Submission #1298244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298244		pucam20102	Knapsack (NOI18_knapsack)	C++20	Compilation error	0 ms	0 KiB

knapsack

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

using ll = long long;

struct Item {
    ll w, v;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll M;
    cin >> N >> M;

    vector<Item> a(N);
    for (int i = 0; i < N; i++) cin >> a[i].w >> a[i].v;

    int n1 = N / 2;
    int n2 = N - n1;

    vector<Item> A(a.begin(), a.begin() + n1);
    vector<Item> B(a.begin() + n1, a.end());
    for (int mask = 0; mask < (1 << n1); mask++) {
        ll w = 0, v = 0;
        for (int i = 0; i < n1; i++)
            if (mask & (1 << i)) w += A[i].w, v += A[i].v;
        if (w <= M) SA.push_back({w, v});
    }

    vector<pair<ll,ll>> SB;
    for (int mask = 0; mask < (1 << n2); mask++) {
        ll w = 0, v = 0;
        for (int i = 0; i < n2; i++)
            if (mask & (1 << i)) w += B[i].w, v += B[i].v;
        if (w <= M) SB.push_back({w, v});
    }
    sort(SB.begin(), SB.end());
    vector<pair<ll,ll>> goodB;
    ll best = -1;
    for (auto &p : SB) {
        if (p.second > best) {
            best = p.second;
            goodB.push_back(p);
        }
    }

    ll ans = 0;

    for (auto &x : SA) {
        ll wA = x.first, vA = x.second;
        ll remain = M - wA;

        int l = 0, r = (int)goodB.size() - 1, pos = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (goodB[m].first <= remain) pos = m, l = m + 1;
            else r = m - 1;
        }

        if (pos != -1)
            ans = max(ans, vA + goodB[pos].second);
        else
            ans = max(ans, vA); 
    }

    cout << ans;
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:30:21: error: 'SA' was not declared in this scope; did you mean 'A'?
   30 |         if (w <= M) SA.push_back({w, v});
      |                     ^~
      |                     A
knapsack.cpp:52:20: error: 'SA' was not declared in this scope; did you mean 'SB'?
   52 |     for (auto &x : SA) {
      |                    ^~
      |                    SB
knapsack.cpp:64:28: error: 'vA' was not declared in this scope; did you mean 'wA'?
   64 |             ans = max(ans, vA + goodB[pos].second);
      |                            ^~
      |                            wA
knapsack.cpp:66:28: error: 'vA' was not declared in this scope; did you mean 'wA'?
   66 |             ans = max(ans, vA);
      |                            ^~
      |                            wA