Submission #5804165

---

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;

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;
}

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;
    }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

Judge Result