Submission #1317906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317906		dex111222333444555	Knapsack (NOI18_knapsack)	C++20	100 / 100	50 ms	1596 KiB

knapsack

#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()

using namespace std;

const int MAXN = 1e5 + 5, MAXW = 2005, MAXV = 1e6 + 6;

template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}

struct S{
    int V, W, K;

    S(int _V = 0, int _W = 0, int _K = 0):
        V(_V), W(_W), K(_K) {};

    bool operator<(const S &other) const {
        return V > other.V;
    }
};

int numVal, numLim, num[MAXW];
long long dp[MAXW];
S val[MAXN];

void input(){
    cin >> numLim >> numVal;
    for(int i = 1; i <= numVal; i++) cin >> val[i].V >> val[i].W >> val[i].K;
}

void solve(){
    sort(val + 1, val + 1 + numVal);

    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;

    for(int i = 1; i <= numVal; i++){
        for(int rep = 0; rep < val[i].K; rep++){
            if (num[val[i].W] * val[i].W > numLim) break;
            num[val[i].W]++;
            for(int sum = numLim - val[i].W; sum >= 0; sum--) if (dp[sum] >= 0)
                maximize(dp[sum + val[i].W], dp[sum] + val[i].V);
        }
    }

    long long res = 0;
    for(int i = 0; i <= numLim; i++) res = max(res, dp[i]);
    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "PASS"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
  int t = 1;
//  cin >> t;
  while(t--){
    input();
    solve();
  }
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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