Submission #879804

#	Time	Username	Problem	Language	Result	Execution time	Memory
879804		TAhmed33	Akcija (COCI21_akcija)	C++98	90 / 110	1913 ms	524288 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[MAXN][MAXN];
bool comb (pair <ll, ll> &a, pair <ll, ll> &b) {
    return a.first == b.first ? a.second < b.second : a.first > b.first;
}
vector <pair <ll, ll>> subs;
void recurse (int pos, int sze, ll cost) {
    if (pos > n) {
        subs.push_back({sze, cost});
        return;
    }
    recurse(pos + 1, sze, cost);
    if (sze + 1 <= a[pos].second) recurse(pos + 1, sze + 1, cost + a[pos].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; });
    if (n <= 20) {
        recurse(1, 0, 0);
        sort(subs.begin(), subs.end(), comb);
        for (int i = 0; i < k; i++) {
            cout << subs[i].first << " " << subs[i].second << '\n';
        }
        return 0;
    }
    for (int j = 0; j <= n + 1; j++) dp[n + 1][j].push_back({0, 0});
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[i + 1][j];
            if (j + 1 <= a[i].second) {
                for (auto [x, y] : dp[i + 1][j + 1]) {
                    dp[i][j].push_back({x + 1, y + a[i].first});
                }
            }
            sort(dp[i][j].begin(), dp[i][j].end(), comb);
            while (dp[i][j].size() > k) dp[i][j].pop_back();
        }
    }
    for (auto [x, y] : dp[1][0]) cout << x << " " << y << '\n';
    //for (int i = 0; i < k; i++) cout << dp[1][0][i].first << " " << dp[1][0][i].second << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |                 for (auto [x, y] : dp[i + 1][j + 1]) {
      |                           ^
Main.cpp:41:36: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             while (dp[i][j].size() > k) dp[i][j].pop_back();
      |                    ~~~~~~~~~~~~~~~~^~~
Main.cpp:44:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     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