Submission #879805

#	Time	Username	Problem	Language	Result	Execution time	Memory
879805		TAhmed33	Akcija (COCI21_akcija)	C++98	90 / 110	1751 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;
}
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][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) continue;
            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';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:20:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |                 for (auto [x, y] : dp[i + 1][j + 1]) {
      |                           ^
Main.cpp:25: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]
   25 |             while (dp[i][j].size() > k) dp[i][j].pop_back();
      |                    ~~~~~~~~~~~~~~~~^~~
Main.cpp:28:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |     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