Submission #879821

#	Time	Username	Problem	Language	Result	Execution time	Memory
879821		TAhmed33	Akcija (COCI21_akcija)	C++98	90 / 110	5025 ms	122960 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 25;
typedef long long ll;
int n; pair <ll, ll> a[MAXN];
vector <pair <ll, ll>> dp[2][MAXN];
bool comb (pair <ll, ll> &a, pair <ll, ll> &b) {
    return a.first == b.first ? a.second < b.second : a.first > b.first;
}
int main () {
    cin >> n; int k; cin >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1, [] (pair <ll, ll> &x, pair <ll, ll> &y) { return x.second < y.second; });
    for (int j = 0; j <= n + 1; j++) dp[(n + 1) & 1][j].push_back({0, 0});
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= n; j++) {
            dp[i & 1][j].clear();
            if (j + 1 > a[i].second) {
                dp[i & 1][j] = dp[(i + 1) & 1][j];
                continue;
            }
            int p1 = 0, p2 = 0;
            vector <pair <ll, ll>> &ret = dp[i & 1][j]; vector <pair <ll, ll>> &c1 = dp[(i + 1) & 1][j];
            vector <pair <ll, ll>> &c2 = dp[(i + 1) & 1][j + 1];
            while ((int)ret.size() < k && p1 < (int)c1.size() && p2 < (int)c2.size()) {
                pair <ll, ll> x = c1[p1], y = {c2[p2].first + 1, c2[p2].second + a[i].first};
                if (comb(x, y)) {
                    ret.push_back(x); p1++;
                } else {
                    ret.push_back(y); p2++;
                }
            }
            while ((int)ret.size() < k && p1 < (int)c1.size()) ret.push_back(c1[p1++]);
            while ((int)ret.size() < k && p2 < (int)c2.size()) {
                ret.push_back({c2[p2].first + 1, c2[p2].second + a[i].first}); p2++;
            }
        }
    }
    for (auto [x, y] : dp[1][0]) cout << x << " " << y << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for (auto [x, y] : dp[1][0]) cout << x << " " << y << '\n';
      |               ^

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