Submission #607063


Source Code Expand

Copy
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll v[222], w[222];
pll ps[1<<16];
ll dp[2][222*1000];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll W;
    cin >> N >> W;
    for (int i = 0; i < N; i++) cin >> v[i] >> w[i];
    if (N <= 30) {
        int n = N/2;
        for (int i = 0; i < 1<<n; i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    sw += w[j];
                    sv += v[j];
                }
            }
            ps[i] = pll(sw, sv);
        }
        sort(ps, ps+(1<<n));
        int m = 1;
        for (int i = 1; i < 1<<n; i++) {
            if (ps[m-1].second < ps[i].second) ps[m++] = ps[i];
        }
        ll res = 0;
        for (int i = 0; i < 1<<(N-n); i++) {
            ll sw = 0, sv = 0;
            for (int j = 0; j < N-n; j++) {
                if ((i>>j)&1) {
                    sw += w[n+j];
                    sv += v[n+j];
                }
            }
            if (sw <= W) {
                ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, 1ll<<55))-1)->second;
                res = max(res, sv+tv);
            }
        }
        cout << res << endl;
        return 0;
    }
    bool flag = true;
    for (int i = 0; i < N; i++) flag &= w[i] <= 1000;
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    if (flag) {
        for (int i = 0; i < N; i++) {
            int cur = i%2, tar = cur^1;
            for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1;
            for (int j = 0; j <= i*1010; j++) {
                if (dp[cur][j] == -1) continue;
                dp[tar][j] = max(dp[tar][j], dp[cur][j]);
                dp[tar][j+w[i]] = max(dp[tar][j+w[i]], dp[cur][j]+v[i]);
            }
        }
        ll ans = 0;
        for (int i = 0; i < 222*1000 && i <= W; i++) {
            ans = max(ans, dp[N%2][i]);
        }
        cout << ans << endl;
    } else {
        for (int i = 0; i < N; i++) {
            int cur = i%2, tar = cur^1;
            for (int j = 0; j <= i*1010; j++) dp[tar][j] = -1;
            for (int j = 0; j <= i*1010; j++) {
                if (dp[cur][j] == -1) continue;
                if (dp[tar][j] == -1 || dp[tar][j] > dp[cur][j]) dp[tar][j] = dp[cur][j];
                if (dp[tar][j+v[i]] == -1 || dp[tar][j+v[i]] > dp[cur][j] + w[i]) dp[tar][j+v[i]] = dp[cur][j]+w[i];
            }
        }
        ll ans = 0;
        for (int i = 0; i < 222*1000; i++) {
            if (dp[N%2][i] != -1 && dp[N%2][i] <= W) ans = i;
        }
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - ナップサック問題
User mayoko
Language C++11 (GCC 4.9.2)
Score 100
Code Size 3266 Byte
Status
Exec Time 106 ms
Memory 5404 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 34 / 34 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 33 / 33 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 33 / 33 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 27 ms 1944 KB
subtask00_sample_2.txt 35 ms 1948 KB
subtask00_sample_3.txt 25 ms 1776 KB
subtask00_sample_4.txt 25 ms 1824 KB
subtask01_0.txt 34 ms 1824 KB
subtask01_1.txt 34 ms 1832 KB
subtask01_10.txt 33 ms 1828 KB
subtask01_11.txt 37 ms 1816 KB
subtask01_12.txt 34 ms 1824 KB
subtask01_13.txt 34 ms 1948 KB
subtask01_14.txt 34 ms 1868 KB
subtask01_2.txt 36 ms 1828 KB
subtask01_3.txt 34 ms 1952 KB
subtask01_4.txt 32 ms 1952 KB
subtask01_5.txt 33 ms 1952 KB
subtask01_6.txt 32 ms 1828 KB
subtask01_7.txt 34 ms 1820 KB
subtask01_8.txt 34 ms 1780 KB
subtask01_9.txt 34 ms 1828 KB
subtask02_0.txt 103 ms 5288 KB
subtask02_1.txt 103 ms 5280 KB
subtask02_10.txt 105 ms 5280 KB
subtask02_11.txt 100 ms 5284 KB
subtask02_12.txt 105 ms 5276 KB
subtask02_13.txt 70 ms 5280 KB
subtask02_14.txt 100 ms 5280 KB
subtask02_2.txt 104 ms 5276 KB
subtask02_3.txt 100 ms 5284 KB
subtask02_4.txt 102 ms 5280 KB
subtask02_5.txt 100 ms 5236 KB
subtask02_6.txt 102 ms 5276 KB
subtask02_7.txt 101 ms 5288 KB
subtask02_8.txt 105 ms 5280 KB
subtask02_9.txt 102 ms 5276 KB
subtask03_0.txt 106 ms 5284 KB
subtask03_1.txt 103 ms 5272 KB
subtask03_10.txt 104 ms 5276 KB
subtask03_11.txt 71 ms 5280 KB
subtask03_2.txt 103 ms 5280 KB
subtask03_3.txt 102 ms 5404 KB
subtask03_4.txt 104 ms 5284 KB
subtask03_5.txt 102 ms 5288 KB
subtask03_6.txt 106 ms 5284 KB
subtask03_7.txt 104 ms 5284 KB
subtask03_8.txt 103 ms 5292 KB
subtask03_9.txt 105 ms 5288 KB