Submission #1303643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303643		srittheboss	Knapsack (NOI18_knapsack)	C++20	100 / 100	63 ms	34356 KiB

knapsack

#include "bits/stdc++.h"
#define ll long long
using namespace std;

const ll MOD = 1e9+7;
const int MAXN = 2e6;

long long fac[MAXN + 1];
long long inv[MAXN + 1];

void setFileIO(const string& filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long exp(long long x, long long n, long long m) {
    x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) { res = res * x % m; }
        x = x * x % m;
        n /= 2;
    }
    return res;
}

void factorial(long long p) {
    fac[0] = 1;
    for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % p; }
}

void inverses(long long p) {
    inv[MAXN] = exp(fac[MAXN], p - 2, p);
    for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % p; }
}

long long choose(long long n, long long r, long long p) {
    return fac[n] * inv[r] % p * inv[n - r] % p;
}

int first_true(int lo, int hi, function<bool(int)> f) {
    hi++;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (f(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int last_true(int lo, int hi, function<bool(int)> f) {
    lo--;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (f(mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}

void solve() {

    ll s, n;
    cin >> s >> n;

    vector<vector<pair<ll, ll>>> items(2001);
    vector<ll> sizes(2001);

    for (ll i = 1; i <= n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        items[b].push_back({a, c});
    }

    for (ll i = 1; i <= s; i++) {
        sort(items[i].begin(), items[i].end(), [](const pair<ll, ll>& a, const pair<ll, ll>& b) {
            return a.first > b.first;
        });
    }

    vector<vector<ll>> dp(s+1, vector<ll>(s+1, 0));


    for (ll i = 1; i <= s; i++) {

        if (items[i].empty()) {
            for (int j = 1; j <= s; j++) {
                dp[i][j] = dp[i - 1][j];
            }
        } else {
            for (ll j=1; j <= s; j++) {
                ll k = 0;
                ll l = 0;
                ll prev = 0;
                ll cumulative_cost = 0;
                while (k*i <= j && !items[i].empty()) {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-k*i] + cumulative_cost);
                    k++;
                    if (k-prev > items[i][l].second) {
                        prev = k-1;
                        l++;
                        if (l >= items[i].size()) break;
                    }

                    cumulative_cost += items[i][l].first;

                }
            }
        }
    }

    cout << dp[s][s] << endl;

}


// Pay attention to constraints
// Do not tunnel vision on one approach
// Do something rather than nothing


int main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    // int t;
    // cin >> t;
    // while (t--) {
         solve();
    // }
}

Compilation message (stderr)

knapsack.cpp: In function 'void setFileIO(const std::string&)':
knapsack.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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