AtCoder Beginner Contest 032

Submission #6912772

Source codeソースコード

#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>(min(max_w, 1000 * n + 1)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1000 * n; j++) {
                dp.at(i + 1).at(j) = max(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(min(max_w, 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) = min(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

Task問題 D - ナップサック問題
User nameユーザ名 megamegane
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 67
Source lengthソースコード長 4141 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 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 0 / 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask00_sample_1.txt AC 1 ms 256 KB
subtask00_sample_2.txt AC 8 ms 1656 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 RE
subtask02_1.txt RE
subtask02_10.txt RE
subtask02_11.txt RE
subtask02_12.txt RE
subtask02_13.txt RE
subtask02_14.txt RE
subtask02_2.txt RE
subtask02_3.txt RE
subtask02_4.txt RE
subtask02_5.txt RE
subtask02_6.txt RE
subtask02_7.txt RE
subtask02_8.txt RE
subtask02_9.txt RE
subtask03_0.txt AC 266 ms 316160 KB
subtask03_1.txt AC 265 ms 316160 KB
subtask03_10.txt AC 265 ms 316160 KB
subtask03_11.txt AC 258 ms 316160 KB
subtask03_2.txt AC 264 ms 316160 KB
subtask03_3.txt AC 265 ms 316160 KB
subtask03_4.txt AC 265 ms 316160 KB
subtask03_5.txt AC 265 ms 316160 KB
subtask03_6.txt AC 265 ms 316160 KB
subtask03_7.txt AC 264 ms 316160 KB
subtask03_8.txt AC 265 ms 316160 KB
subtask03_9.txt AC 266 ms 316160 KB