Submission #1244910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244910		youssef97_	Knapsack (NOI18_knapsack)	C++20	100 / 100	71 ms	33268 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

void shawerma() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef frenchfries
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
    //freopen("PROBLEMNAME.in", "r", stdin);
}


#define fi first
#define se second
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define eb emplace_back
#define pb push_back
#define popb pop_back
#define popf pop_front
#define pf push_front
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define vi vector<int>
#define vll vector<long long>
#define vpii vector<pair<int, int>>
#define vpll vector<pair<long long, long long>>
#define vs vector<string>
#define vb vector<bool>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vvc vector<vector<char>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define Ones(n) __builtin_popcount(n)
typedef long double ld;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dy[] = {-1, 1, 0, 0, 1, 1, -1, -1};
char di[] = {'L', 'R', 'U', 'D'};
int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int ky[] = {1, 2, 2, 1, -1, -2, -2, -1};


const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5, M = 2e5 + 5, INF = 1e18;
const ld PI = acos(-1);


void Solve() {
    int balance, n;
    cin >> balance >> n;
    map<int, vpii> mp;
    for (int i = 0; i < n; ++i) {
        int val, sz;
        ll k;
        cin >> val >> sz >> k;
        if (sz <= balance && k > 0) mp[sz].pb({val, k});
    }

    vvll dp(mp.size() + 1, vll(balance + 1, -INF));
    dp[0][0] = 0;

    int at = 1;
    for (auto &[w, items]: mp) {
        sort(allr(items));
        for (int lim = 0; lim <= balance; ++lim) {
            // option 1 : leave it
            dp[at][lim] = dp[at - 1][lim];

            //option 2: take it

            int copies = 0, type_at = 0, used = 0;
            ll profit = 0;
            while ((copies + 1) * w <= lim && type_at < items.size()) {
                copies++;
                profit += items[type_at].fi;

                // check if past was seen before to maximize either now, or then but with current's value increase?
                if (dp[at - 1][lim - copies * w] != -INF) {
                    dp[at][lim] = max(dp[at][lim], dp[at - 1][lim - copies * w] + profit);
                }
                used++;
                if(used == items[type_at].se){
                    used = 0;
                    type_at++;
                }
            }
        }
        at++;
    }

    cout << *max_element(all(dp.back())) << '\n';
}

int main() {
    shawerma();
    int t = 1;
    //cin >> t;
    while (t--) {
        Solve();
    }
}

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