Submission #6906956


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

bool isOK(int index, long long key, const vector<pair<long long, long long>> &v) {
    return v.at(index).first <= key;
}

int binary_search(long long key, const vector<pair<long long, long long>> &v) {
    int ng = (int)v.size();
    int ok = 0;

    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key, v)) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main() {
    int n, max_w;
    cin >> n >> max_w;
    vector<long long> v(n), w(n);
    bool w_lower_1000 = true;
    for (int i = 0; i < n; i++) {
        cin >> v.at(i) >> w.at(i);
        if (w.at(i) > 1000) w_lower_1000 = false;
    }

    if (n <= 30) {
        if (n > 20) {
            vector<pair<long long, long long>> groupA(0);
            for (int bit = 0; bit <= (1 << 15) - 1; bit++) {
                long long sum_w = 0, sum_v = 0;
                for (int i = 0; i < 15; i++) {
                    if (bit & (1 << i)) {
                        sum_w += w.at(i);
                        sum_v += v.at(i);
                    }
                }
                groupA.push_back(make_pair(sum_w, sum_v));
            }
            
            vector<pair<long long, long long>> groupB(0);
            for (int bit = 0; bit <= (1 << (n - 15)) - 1; bit++) {
                long long sum_w = 0, sum_v = 0;
                for (int i = 0; i < n - 15; i++) {
                    if ((bit << 15) & ((1 << i) << 15)) {
                        sum_w += w.at(i + 15);
                        sum_v += v.at(i + 15);
                    }
                }
                groupB.push_back(make_pair(sum_w, -sum_v));
            }
            sort(groupB.begin(), groupB.end());
            long long m = 0;
            for (int i = 0; i < (int)groupB.size(); i++) {
                m = max(m, -groupB.at(i).second);
                groupB.at(i).second = m;
            }
            
            long long ans = 0;
            for (int i = 0; i < (int)groupA.size(); i++) {
                if (groupA.at(i).first > max_w) continue;

                int index = binary_search(max_w - groupA.at(i).first, groupB);
                long long sum = groupA.at(i).second + groupB.at(index).second;
                ans = max(ans, sum);
            }
            cout << ans << endl;
        }
        else {
            long long ans = 0;
            for (int bit = 0; bit < (1 << n) - 1; bit++) {
                long long sum_w = 0, sum_v = 0;
                for (int i = 0; i < n; i++) {
                    if (bit & (1 << i)) {
                        sum_w += w.at(i);
                        sum_v += v.at(i);
                    }
                }
                if (sum_w <= max_w) ans = max(ans, sum_v);
            }
            cout << ans << endl;
        }
    }
    else if (w_lower_1000) {
        vector<vector<long long>> dp(n + 1, vector<long long>(1000 * n + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1000 * n; j++) {
                dp.at(i + 1).at(j) = dp.at(i).at(j);
                if (j - w.at(i) >= 0) dp.at(i + 1).at(j) = max(dp.at(i + 1).at(j), dp.at(i).at(j - w.at(i)) + v.at(i));
            }
        }
        cout << dp.at(n).at(1000 * n) << endl;
    }
    else {
        const long long INF = 1ll << 60;
        vector<vector<long long>> dp(n + 1, vector<long long>(1000 * n + 1, INF));
        dp.at(0).at(0) = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1000 * n; j++) {
                dp.at(i + 1).at(j) = dp.at(i).at(j);
                if (j - v.at(i) >= 0 && dp.at(i).at(j - v.at(i)) < INF) dp.at(i + 1).at(j) = min(dp.at(i + 1).at(j), dp.at(i).at(j - v.at(i)) + w.at(i));
            }
        }

        long long ans = 0;
        for (long long i = 0; i <= 1000 * n; i++) {
            if (dp.at(n).at(i) <= max_w) ans = max(ans, i);
        }
        cout << ans << endl;
    }
}       

Submission Info

Submission Time
Task D - ナップサック問題
User karyo
Language C++14 (GCC 5.4.1)
Score 67
Code Size 4067 Byte
Status WA
Exec Time 311 ms
Memory 316160 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 0 / 33 33 / 33
Status
AC × 4
AC × 19
AC × 3
WA × 14
AC × 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 AC 1 ms 256 KB
subtask00_sample_2.txt AC 8 ms 1528 KB
subtask00_sample_3.txt AC 1 ms 256 KB
subtask00_sample_4.txt AC 1 ms 256 KB
subtask01_0.txt AC 8 ms 1528 KB
subtask01_1.txt AC 8 ms 1528 KB
subtask01_10.txt AC 8 ms 1528 KB
subtask01_11.txt AC 8 ms 1528 KB
subtask01_12.txt AC 8 ms 1528 KB
subtask01_13.txt AC 8 ms 1528 KB
subtask01_14.txt AC 8 ms 1528 KB
subtask01_2.txt AC 8 ms 1528 KB
subtask01_3.txt AC 8 ms 1528 KB
subtask01_4.txt AC 7 ms 1528 KB
subtask01_5.txt AC 10 ms 1528 KB
subtask01_6.txt AC 7 ms 1528 KB
subtask01_7.txt AC 8 ms 1528 KB
subtask01_8.txt AC 8 ms 1528 KB
subtask01_9.txt AC 8 ms 1528 KB
subtask02_0.txt WA 291 ms 316160 KB
subtask02_1.txt WA 291 ms 316160 KB
subtask02_10.txt WA 291 ms 316160 KB
subtask02_11.txt WA 291 ms 316160 KB
subtask02_12.txt WA 290 ms 316160 KB
subtask02_13.txt AC 311 ms 316160 KB
subtask02_14.txt WA 291 ms 316160 KB
subtask02_2.txt WA 291 ms 316160 KB
subtask02_3.txt WA 292 ms 316160 KB
subtask02_4.txt WA 291 ms 316160 KB
subtask02_5.txt WA 290 ms 316160 KB
subtask02_6.txt WA 291 ms 316160 KB
subtask02_7.txt WA 290 ms 316160 KB
subtask02_8.txt WA 290 ms 316160 KB
subtask02_9.txt WA 292 ms 316160 KB
subtask03_0.txt AC 246 ms 316160 KB
subtask03_1.txt AC 244 ms 316160 KB
subtask03_10.txt AC 245 ms 316160 KB
subtask03_11.txt AC 238 ms 316160 KB
subtask03_2.txt AC 245 ms 316160 KB
subtask03_3.txt AC 245 ms 316160 KB
subtask03_4.txt AC 245 ms 316160 KB
subtask03_5.txt AC 245 ms 316160 KB
subtask03_6.txt AC 245 ms 316160 KB
subtask03_7.txt AC 245 ms 316160 KB
subtask03_8.txt AC 244 ms 316160 KB
subtask03_9.txt AC 246 ms 316160 KB