Submission #1292076

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

knapsack

#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;
const int MAXS = 2005, MAXN = 1e5 + 5, 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 numVal, lim, val[MAXN], weight[MAXN], num[MAXN], used[MAXS];
long long dp[MAXS];
vector<int> can[MAXN];

void input(){
    cin >> lim >> numVal;
    for(int i = 1; i <= numVal; i++){
        cin >> val[i] >> weight[i] >> num[i];
        int sum = 0;
        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(){
    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i <= numVal; i++){
        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[j] > -inf){
                maximize(dp[j + weight[i] * can[i][k]], dp[j] + 1LL * val[i] * 1LL * can[i][k]);
            }
        }
    }
    long long res = -inf;
    for(int i = 0; i <= lim; i++) maximize(res, dp[i]);
    cout << res << '\n';
}

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