Submission #1070434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070434		seoul_korea	Knapsack (NOI18_knapsack)	C++17	73 / 100	1097 ms	18636 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const bool multiTest = 0;
#define TASK ""
mt19937 rng(time(0));

const int maxN = 2222;

struct Pack {
    ll w, v;
};

ll totalW;
int n;
vector<Pack> packs;
ll dp[maxN];

void solve(int curTest) {
    //cerr << "\n>TEST #" << curTest << "<\n";
    // GET AC PLEASE
    cin >> totalW >> n;
    for(int i = 1; i <= n; i++) {
        ll v, w, k;
        cin >> v >> w >> k;
        int phanTach = 1;
        while(k - phanTach >= 0) {
            packs.push_back({w * phanTach, v * phanTach});
            k -= phanTach;
            phanTach *= 2;
        }
        if(k > 0) packs.push_back({w * k, v * k});
    }
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for(auto pack : packs) {
        for(ll s = totalW; s >= pack.w; s--) {
            dp[s] = max(dp[s], dp[s - pack.w] + pack.v);
        }
    }
    cout << *max_element(dp, dp + totalW + 1) << endl;
}

main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);

    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    int nTest = 1;
    if(multiTest) cin >> nTest;
    for(int iTest = 1; iTest <= nTest; iTest++) solve(iTest);

    return 0;
}

Compilation message (stderr)

knapsack.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main() {
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:49:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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