Submission #1165017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165017		abdullah_	Knapsack (NOI18_knapsack)	C++20	100 / 100	870 ms	3172 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef pair<int, int> pp;



#define all(a) (a).begin(), (a).end()


#define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e15;

/*
1- Read input
2- val, k

3- numIdx = s / i.

4- If i

*/

void solve() {
    int s, n;
    cin >> s >> n;


    vector<vector<pp> > cur(s + 1);
    for(int i = 0, val, w, k; i < n; ++i) {
        cin >> val >> w >> k;
        cur[w].push_back({val, k});
    }

    for(int i = 1; i <= s; ++i) {
        sort(cur[i].rbegin(), cur[i].rend());
    }

    
    vector<vector<int> > a(s + 1);

    for(int i = 1; i <= s; ++i) {
        a[i].assign((s / i) + 2, 0);

        int idx = 1;

        for(auto [val, k] : cur[i]) {
            while(idx < a[i].size() and k) {
                a[i][idx] = val + a[i][idx - 1];
                idx++;
                k--;
            }
        }

    }


    /*
        Taking one or two or 3
        W and val


    */

    // cout << a[1][1] << '\n';


    vector<vector<pp> > ans(s + 1, vector<pp> (2, {-INF, 0}));

    ans[0][0] = ans[0][1] = {0, 0};

    for(int i = 1; i <= s; ++i) {
        for(int idx = 1; idx < a[i].size(); ++idx) {

            // if(a[i][idx] == a[i][idx-1])    break;

            int val = a[i][idx];
            int w = (idx) * i;
            // cout << val << ' ';
            for(int j = s; j >= w; --j) {
                if(ans[j-w][0].second != i)
                    ans[j].push_back({val + ans[j - w][0].first, i});
                if(ans[j-w][1].second != i)
                    ans[j].push_back({val + ans[j - w][1].first, i});

                sort(ans[j].rbegin(), ans[j].rend());

                vector<pp> t;
                for(auto [x, y] : ans[j]) {
                    if(t.empty() or t.back().second != y) 
                        t.push_back({x, y});
                }

                ans[j] = t;

                while(ans[j].size() > 2) {  
                    ans[j].pop_back();
                }

            }


        }
        // int val = 0;

        // for(auto &v : ans) {
        //     for(auto [x, y] : v) {
        //         val = max(val, x);
        //     }
        // }

        // cout << val << endl;
    }

    int val = 0;

    for(auto &v : ans) {
        for(auto [x, y] : v) {
            val = max(val, x);
        }
    }

    cout << val << endl;
    // cout << *max_element(all(ans)) << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }

    return 0;
}

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