Submission #1158942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158942		anomori	Knapsack (NOI18_knapsack)	C++20	0 / 100	1096 ms	320 KiB

knapsack

#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#define fin cin
#define fout cout

using namespace std;

//ifstream fin("zaruri.in");
//ofstream fout("zaruri.out");

using dbl = double;
using ll = long long;
using ull = unsigned long long;

const int nmax = 1e5+1;

struct cv {
    int weight;
    int cost;
    int available;
};

int n,s;
ll dp[nmax];
int main() {
    fin >> s >> n;
    vector<cv> v(n);
    for (auto& [y,x,z] : v) {
        fin >> x >> y >> z;
    }
    ll ans = 0;
    for (const auto [weight, cost, available] : v) {
        for (int k = 1; k <= available; k++) {
            for (int w = s; w >= 0; w--) {
                if (dp[w] and w + weight <= s) {
                    dp[w + weight] = max(dp[w] + cost, dp[w + weight]);
                    ans = max(ans, dp[w + weight]);
                }
            }
            dp[weight] = max(dp[weight], 1ll*cost);
        }
    }
    fout << ans;


    return 0;
}

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