Submission #1292271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292271		dex111222333444555	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	11932 KiB

knapsack

#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
const int MAXN = 1e5 + 5, MAXS = 2005, LOG = 31;
const long long inf = 1e18 + 3;
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}
int lim, numVal, val[MAXN], weight[MAXN], num[MAXN], used[MAXS];
long long dp[2][MAXS];
vector<int> can[MAXN];

void calcDP(){
    memset(dp[0], -0x3f, sizeof dp[0]);
    dp[0][0] = 0;
    for(int i = 1; i <= numVal; i++){
        if (lim / weight[i] <= 20){
            for(int k = 0; k < can[i].size(); k++){
                for(long long j = lim - 1LL * weight[i] * 1LL * can[i][k]; j >= 0; j--) if (dp[0][j] > -inf){
                    maximize(dp[0][j + weight[i] * can[i][k]], dp[0][j] + 1LL * val[i] * 1LL * can[i][k]);
                }
            }
        }else{
            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++) maximize(dp[0][j], dp[1][j]);
        }
    }
    long long res = -inf;
    for(int i = 0; i <= lim; i++) res = max(res, dp[0][i]);
    cout << res << '\n';
}

void input(){
    cin >> lim >> numVal;
    for(int i = 1; i <= numVal; i++){
        cin >> val[i] >> weight[i] >> num[i];
        int sum = 0;
        num[i] = min(num[i], lim / weight[i]);
        for(int j = 0; j < 31 - __builtin_clz(num[i]); j++){
            can[i].push_back(MASK(j)); sum += MASK(j);
        }

        int m = num[i] - sum;
        for(int b = 0; b < LOG; b++) if (BIT(m, b)){
            can[i].push_back(MASK(b));
        }
    }
}

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:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         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