Submission #1163551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163551		jmuzhen	Akcija (COCI21_akcija)	C++20	90 / 110	5089 ms	18252 KiB

Main

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

constexpr bool DEBUG = 0;

#define int long long
#define printPair(x) x.first << " " << x.second
#define cerr if(DEBUG) cerr

int n, k;

struct Item {
    int w, d;
};

vector<Item> S;

vector<vector<int>> dp;

void print(vector<int> v) {
    if (!DEBUG) return;
    for (int x : v)  cout << x << " ";
    cout << endl;
}
vector<int> mergeAns(vector<int> a, vector<int> b, int k) {
    cerr<<"a";print(a);
    cerr<<"b";print(b);
    int i = 0, j = 0;
    vector<int> res;
    while ((i < a.size() || j < b.size())
           && res.size() < k
           )
    {
        cerr << i << " " << j << " " << res.size() << endl;
        if (i < a.size() && (j == b.size() || a[i] <= b[j])) {
            res.push_back(a[i]);
            i++;
        }
        else {
            res.push_back(b[j]);
            j++;
        }
    }

    return res;
}

signed main() {
    cin >> n >> k;

    dp.resize(n+1, vector<int>());

    for (int i = 0; i < n; i++) {
        int w, d; cin >> w >> d;
        S.push_back({w, d});
    }

    sort(S.begin(), S.end(), [](Item&a, Item&b) {
         return a.d != b.d ? a.d < b.d : a.w < b.w;
     });

    // let dp[L] = the list of possible subset prices if we want a subset of exactly length L
    // observe that we just need to store the min k values
    // then to satisfy the time constraint, notice that we can only add an item to a subset
    // iff the item's d is less than the subset length

    dp[0] = {0};
    for (int i = 0; i < n; i++) { // look at each item
        cerr << "looking at " << i << endl;
        int L = min(i+1, S[i].d); // maximum value of L for this item
        for (int j = L; j >= 1; j--) {
            // we can either
            // - NOT take i, i.e. simply use the current values stored in dp[j],
            // - or TAKE i, i.e. look at dp[j-1] and add w to each value there
            // finally to combine these 2 cases we merge them together, taking the min k values

            vector<int> case1 = dp[j];
            vector<int> case2 = dp[j-1];
            for (int& x : case2) x += S[i].w;
            cerr << i << " " << j << endl;

            dp[j] = mergeAns(case1, case2, k);
            cerr<<"dp[j] = ";print(dp[j]);
        }
    }

    // then we get the top k values, starting from longer subsets first
    int cnt = 0;
    int L = n;
    while (cnt < k && L >= 0) {
        int j = 0;
        while (cnt < k && j < dp[L].size()) {
            cout << L << " " << dp[L][j] << endl;
            j++;
            cnt++;
        }
        L--;
    }

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 0 / 20