Submission #5805203
Source Code Expand
#include<bits/stdc++.h> #define REP(i,n) for(int i = 0; i < n; i++) #define RREP(i,n) for(int i = n-1; i >= 0; i--) using namespace std; typedef long long ll; ll N, W; vector<ll> Value, Weight; pair<ll, ll> ps[1 << (30/2)]; //重さ、価値 /* ll rec(int point, ll v, ll w){ if(point >= N){ return v; }else{ if(w + Weight[point] > W) return rec(point+1,v,w); else{ return max(rec(point+1, v, w), rec(point+1,v + Value[point], w + Weight[point])); } } return 0; }*/ void solve(){ //前半全列挙 int n2 = N / 2; for(int i = 0; i < 1 << n2; i++){ ll sw = 0, sv = 0; for(int j = 0; j < n2; j++){ if(i >> j & 1){ sw += Weight[j]; sv += Value[j]; } } ps[i] = make_pair(sw,sv); } //ムダな要素を省く sort(ps, ps + (1 << n2)); int m = 1; for(int i = 1; i < 1 << n2; i++){ if(ps[m-1].second < ps[i].second){ ps[m++] = ps[i]; } } //後ろ半分を全列挙し解を求める ll res = 0; for(int i = 0; i < 1 << (N - n2); i++){ ll sw = 0, sv = 0; for(int j = 0; j < N - n2; j++){ if(i >> j & 1){ sw += Weight[n2 + j]; sv += Value[n2 + j]; } } if(sw <= W){ ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second; res = max(res, sw + tv); } } printf("%lld\n", res); } int main(){ cin >> N >> W; REP(i,N){ int v, w; cin >> v >> w; Value.push_back(v); Weight.push_back(w); } if(N <= 30){ //cout << rec(0,0,0) << endl;//これだとWがデカイ時にあかん。 solve(); }else{ bool flag = 1; REP(i,N){ if(Weight[i] >1000 || Weight[i] < 0) flag = 0; } if(flag){//weight1000以下 ll dpw[1001] = {0};//重さw以下で最大の価値 REP(i,N){ RREP(j, W+1){ if(j-Weight[i] >= 0) dpw[j] = max(dpw[j], dpw[j-Weight[i]] + Value[i]); } } cout << dpw[W] << endl; }else{//value 1000以下 ll dpv[200001] = {0};//価値v以上で最小の重さ REP(i,N){ RREP(j, 200001){ if(j-Value[i] >= 0) dpv[j] = min(dpv[j], dpv[j-Value[i]] + Weight[i]); } } REP(i, 200001){ if(dpv[i] > W){ cout << dpv[i-1] << endl; break; } } } } }
Submission Info
Submission Time | |
---|---|
Task | D - ナップサック問題 |
User | raoZ |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2801 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void solve()’: ./Main.cpp:57:64: error: ‘INF’ was not declared in this scope ll tv = (lower_bound(ps, ps + m, make_pair(W - sw, INF)) - 1)->second; ^