Submission #1180907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180907		abdelaal_03	Knapsack (NOI18_knapsack)	C++20	0 / 100	157 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef long long ll;
const long double PI = 3.141592654;
const long long md = 998244353;


#define xi first
#define yi second
#define MAX 300007
#define INF (ll)1e18
#define SQ 500

long long gcd(long long a, long long b) {
    if (b == 0)return a;
    return (a % b) ? gcd(b, a % b) : b;
}
ll dp[1007][5000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll n, W;
    cin>>n>>W;
    vector<ll> w(n + 1), v(n + 1), k(n + 1);
    for (int i = 1; i<= n; i++) {
        ll wi, vi, ki;
        cin>>vi>>wi>>ki;
        w[i] = wi;
        v[i] = vi;
        k[i] = ki;
    }
    for (int i = 1;i <= n; i++) {
        set<pair<ll, ll>>s[w[i]];
        for (int j = 0; j <= W; j++){
            dp[i][j] = dp[i - 1][j];
            ll rem = j % w[i];
            if (s[rem].size() > k[i]) {
                ll idx = j - (k[i] + 1) * w[i];
                ll ow = dp[i - 1][idx] * w[i] - idx * v[i];
                auto it = s[rem].find({ow, idx});
                s[rem].erase(it);
            }
            if (!s[rem].empty()) dp[i][j] = max(dp[i][j], (s[rem].rbegin()->xi + j * v[i]) / w[i]);
            ll nw = dp[i - 1][j] * w[i] - j * v[i];
            s[rem].insert({nw, j});
        }
    }
    cout<<dp[n][W]<<endl;

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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