Submission #3003410


Source Code Expand

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
int n;
ll W;
int v[201], w[201];
ll dp[201][200001];
ll vsum = 0;

bool comp(const Pll &a, const Pll &b){
		if(a.first != b.first)return a.first > b.first;
		else return a.second > b.second;
}

ll calc1(){
		vector<Pll> vec;
		for(int i = 0; i < (1 << (n / 2)); i++){
				ll wtmp = 0;
				ll vtmp = 0;
				for(int j = 0; j < n / 2; j++){
						if((i >> j) % 2 == 1){
								wtmp += w[j];
								vtmp += v[j];
						}
				}
				if(wtmp <= W)vec.pb(mk(wtmp, vtmp));
		}
		sort(vec.begin(), vec.end(), comp);
		ll res = 0;
		for(int i = 0; i < (1 << (n - n / 2)); i++){
				ll wtmp = 0;
				ll vtmp = 0;
				for(int j = 0; j < n - n / 2; j++){
						if((i >> j) % 2 == 1){
								wtmp += w[n / 2 + j];
								vtmp += v[n / 2 + j];
						}
				}
				if(wtmp <= W){
						int index = lower_bound(vec.begin(), vec.end(), mk(W-wtmp, linf), comp) - vec.begin();
						for(int j = index; j < vec.size(); j++){
								res = max(res, vtmp + vec[j].second);
						}
				}
		}
		return res;
}

ll calc2(){
		for(int i = 0; i < n; i++){
				dp[i+1][0] = 0;
				for(int j = 1; j <= W; j++){
						dp[i+1][j] = dp[i][j];
						if(j - w[i] >= 0)dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]);
				}
		}
		ll res = 0;
		for(int j = 1; j <= W; j++){
				res = max(res, dp[n][j]);
		}
		return res;
}

ll calc3(){
		for(int i = 0; i <= n; i++){
				for(int j = 0; j <= vsum; j++){
						dp[i][j] = linf;
				}
		}
		dp[0][0] = 0;
		for(int i = 0; i < n; i++){
				dp[i+1][0] = 0;
				for(int j = 1; j <= vsum; j++){
						dp[i+1][j] = dp[i][j];
						if(j - v[i] >= 0)dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i]);
				}
		}
		ll res = 0;
		for(int i = 0; i <= vsum; i++){
				if(dp[n][i] <= W)res = i;
		}
		return res;
}

int main(int argc, char const* argv[])
{
	cin >> n >> W;
	ll wsum = 0;
	for(int i = 0; i < n; i++)cin >> v[i] >> w[i];
	for(int i = 0; i < n; i++)wsum += w[i];
	for(int i = 0; i < n; i++)vsum += v[i];
	if(n <= 30)cout << calc1() << endl;
	else if(wsum <= 200000)cout << calc2() << endl;
	else cout << calc3() << endl;
	return 0;
}

Submission Info

Submission Time
Task D - ナップサック問題
User fumiphys
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2567 Byte
Status AC
Exec Time 1058 ms
Memory 312832 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 33 / 33 33 / 33
Status
AC × 4
AC × 19
AC × 17
AC × 14
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 1 ms 256 KB
subtask00_sample_2.txt AC 6 ms 256 KB
subtask00_sample_3.txt AC 1 ms 256 KB
subtask00_sample_4.txt AC 1 ms 256 KB
subtask01_0.txt AC 6 ms 256 KB
subtask01_1.txt AC 6 ms 256 KB
subtask01_10.txt AC 6 ms 256 KB
subtask01_11.txt AC 6 ms 256 KB
subtask01_12.txt AC 6 ms 256 KB
subtask01_13.txt AC 6 ms 256 KB
subtask01_14.txt AC 6 ms 256 KB
subtask01_2.txt AC 6 ms 256 KB
subtask01_3.txt AC 6 ms 256 KB
subtask01_4.txt AC 6 ms 256 KB
subtask01_5.txt AC 1058 ms 892 KB
subtask01_6.txt AC 6 ms 256 KB
subtask01_7.txt AC 6 ms 256 KB
subtask01_8.txt AC 6 ms 256 KB
subtask01_9.txt AC 6 ms 256 KB
subtask02_0.txt AC 91 ms 312064 KB
subtask02_1.txt AC 66 ms 311680 KB
subtask02_10.txt AC 66 ms 311680 KB
subtask02_11.txt AC 71 ms 311808 KB
subtask02_12.txt AC 74 ms 311808 KB
subtask02_13.txt AC 61 ms 311552 KB
subtask02_14.txt AC 63 ms 311552 KB
subtask02_2.txt AC 85 ms 312064 KB
subtask02_3.txt AC 66 ms 311680 KB
subtask02_4.txt AC 85 ms 312064 KB
subtask02_5.txt AC 63 ms 311552 KB
subtask02_6.txt AC 81 ms 312064 KB
subtask02_7.txt AC 74 ms 311808 KB
subtask02_8.txt AC 66 ms 311680 KB
subtask02_9.txt AC 81 ms 312064 KB
subtask03_0.txt AC 106 ms 312832 KB
subtask03_1.txt AC 104 ms 312832 KB
subtask03_10.txt AC 103 ms 312832 KB
subtask03_11.txt AC 61 ms 311552 KB
subtask03_2.txt AC 102 ms 312832 KB
subtask03_3.txt AC 103 ms 312832 KB
subtask03_4.txt AC 103 ms 312832 KB
subtask03_5.txt AC 103 ms 312832 KB
subtask03_6.txt AC 103 ms 312832 KB
subtask03_7.txt AC 102 ms 312832 KB
subtask03_8.txt AC 100 ms 312704 KB
subtask03_9.txt AC 104 ms 312832 KB