Submission #838861

#	Time	Username	Problem	Language	Result	Execution time	Memory
838861		Achilles1	Knapsack (NOI18_knapsack)	C++17	100 / 100	117 ms	64332 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define Sellihca ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
#define M 1000000007
const int N = 1e5 + 2;

struct p {
    int val, w, c;
};

void Sellihca1() {
    int n, s;
    int val, w, c;
    int mxw = 0;
    cin >> s >> n;
    vector<pair<int, int>> weights[2000 + 1];
    for (int i = 1; i <= n; ++i) {
        cin >> val >> w >> c;
        mxw = max(mxw, w);
        c = min(c, 2000);
        weights[w].emplace_back(val, c);
    }

    ll p[2001][2001];

    memset(p, 0, sizeof p);

    for (int i = 0; i <= 2000; ++i) {
        std::sort(weights[i].begin(), weights[i].end(), greater<>());
    }

    for (int i = 0; i <= 2000; ++i) {
        int idx = 0;
        for (int j = 0; idx < weights[i].size() && j < 2000; ++j) {
            p[i][j] = weights[i][idx].first;
            weights[i][idx].second--;
            if (!weights[i][idx].second) idx++;
        }
        for (int j = 1; j <= 2000; ++j) {
            p[i][j] += p[i][j - 1];
        }
    }


    ll dp[2001][2001];
    memset(dp, -1, sizeof dp);

    dp[0][0] = 0;

    for (int weight = 1; weight <= mxw; ++weight) {
        for (int pick = s; pick >= 0; --pick) {
            for (int cnt = 1; cnt <= s / weight; ++cnt) {
                dp[weight][pick] = max(dp[weight][pick], dp[weight - 1][pick]);

                if (pick - weight * cnt >= 0 && ~(dp[weight - 1][pick - weight * cnt]))
                    dp[weight][pick] = max(dp[weight][pick], dp[weight - 1][pick - weight * cnt] + p[weight][cnt-1]);
            }
        }
    }

    ll ans = 0;

    for (int i = 1; i <= 2000; ++i) {
        ans = max(ans, dp[i][s]);
    }

    cout << ans;

}

int main() {
    Sellihca
    int t = 1;
//    cin >> t;
    while (t--) {
        Sellihca1();
    }
}

Compilation message (stderr)

knapsack.cpp: In function 'void Sellihca1()':
knapsack.cpp:37:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = 0; idx < weights[i].size() && j < 2000; ++j) {
      |                         ~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27