Submission #879810

#	Time	Username	Problem	Language	Result	Execution time	Memory
879810		TAhmed33	Akcija (COCI21_akcija)	C++98	90 / 110	5043 ms	236548 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();
            dp[i & 1][j] = dp[(i + 1) & 1][j];
            if (j + 1 > a[i].second) continue;
            if (j + 1 <= a[i].second) {
                for (auto [x, y] : dp[(i + 1) & 1][j + 1]) {
                    dp[i & 1][j].push_back({x + 1, y + a[i].first});
                }
            }
            sort(dp[i & 1][j].begin(), dp[i & 1][j].end(), comb);
            while ((int)dp[i & 1][j].size() > k) dp[i & 1][j].pop_back();
        }
    }
    for (auto [x, y] : dp[1][0]) cout << x << " " << y << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:21:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |                 for (auto [x, y] : dp[(i + 1) & 1][j + 1]) {
      |                           ^
Main.cpp:29:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     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