Submission #1292169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292169		dex111222333444555	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	1588 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5, MAXS = 2005;
const long long inf = 1e18 + 3;
int lim, numVal, val[MAXN], weight[MAXN], num[MAXN];
long long dp[2][MAXS];

void calcDP(){
    memset(dp[0], -0x3f, sizeof dp[0]);
    dp[0][0] = 0;
    for(int i = 1; i <= numVal; i++){
        memset(dp[1], -0x3f, sizeof dp[1]);
        for(int rem = 0; rem < weight[i]; rem++){
            deque<pair<int, long long>> dq;
            for(int j = 0; rem + j * weight[i] <= lim; j++){
                int nxt = rem + j * weight[i];
                long long save = dp[0][nxt] - j * val[i];

                while(dq.size() && dq.back().second <= save)
                    dq.pop_back();

                dq.push_back({j, save});

                while(dq.size() && dq.front().first < j - num[i])
                    dq.pop_front();

                dp[1][nxt] = dq.front().second + j * val[i];
            }
        }
        for(int j = 0; j <= lim; j++) dp[0][j] = dp[1][j];
    }
    long long res = -inf;
    for(int i = 0; i <= lim; i++) res = max(res, dp[1][i]);
    cout << res << '\n';
}

void input(){
    cin >> lim >> numVal;
    for(int i = 1; i <= numVal; i++)
        cin >> val[i] >> weight[i] >> num[i];
}

void solve(){
    calcDP();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "teest"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
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