Submission #5805222


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;

static const ll INF = 1 << 21;

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 2833 Byte
Status WA
Exec Time 49 ms
Memory 1792 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 0 / 34 0 / 33 0 / 33
Status
WA × 4
AC × 2
WA × 17
AC × 15
WA × 2
WA × 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 WA 1 ms 256 KB
subtask00_sample_2.txt WA 7 ms 768 KB
subtask00_sample_3.txt WA 1 ms 256 KB
subtask00_sample_4.txt WA 1 ms 256 KB
subtask01_0.txt WA 6 ms 768 KB
subtask01_1.txt WA 7 ms 768 KB
subtask01_10.txt WA 6 ms 768 KB
subtask01_11.txt WA 7 ms 768 KB
subtask01_12.txt WA 7 ms 768 KB
subtask01_13.txt WA 7 ms 768 KB
subtask01_14.txt WA 6 ms 768 KB
subtask01_2.txt AC 6 ms 768 KB
subtask01_3.txt WA 7 ms 768 KB
subtask01_4.txt AC 6 ms 768 KB
subtask01_5.txt WA 6 ms 768 KB
subtask01_6.txt WA 6 ms 768 KB
subtask01_7.txt WA 7 ms 768 KB
subtask01_8.txt WA 7 ms 768 KB
subtask01_9.txt WA 6 ms 768 KB
subtask02_0.txt AC 26 ms 1024 KB
subtask02_1.txt AC 6 ms 384 KB
subtask02_10.txt AC 6 ms 384 KB
subtask02_11.txt AC 9 ms 512 KB
subtask02_12.txt AC 12 ms 512 KB
subtask02_13.txt AC 1 ms 256 KB
subtask02_14.txt AC 3 ms 256 KB
subtask02_2.txt AC 21 ms 768 KB
subtask02_3.txt AC 5 ms 384 KB
subtask02_4.txt AC 21 ms 896 KB
subtask02_5.txt AC 3 ms 256 KB
subtask02_6.txt AC 18 ms 768 KB
subtask02_7.txt AC 12 ms 512 KB
subtask02_8.txt AC 6 ms 384 KB
subtask02_9.txt AC 18 ms 768 KB
subtask03_0.txt WA 49 ms 1792 KB
subtask03_1.txt WA 49 ms 1792 KB
subtask03_10.txt WA 49 ms 1792 KB
subtask03_11.txt WA 49 ms 1792 KB
subtask03_2.txt WA 49 ms 1792 KB
subtask03_3.txt WA 49 ms 1792 KB
subtask03_4.txt WA 49 ms 1792 KB
subtask03_5.txt WA 49 ms 1792 KB
subtask03_6.txt WA 49 ms 1792 KB
subtask03_7.txt WA 49 ms 1792 KB
subtask03_8.txt WA 49 ms 1792 KB
subtask03_9.txt WA 49 ms 1792 KB