Submission #3003352

---

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];
int dp[201][200001];

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(){

}

ll calc3(){

}

int main(int argc, char const* argv[])
{
	cin >> n >> W;
	ll vsum = 0;
	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

Judge Result