oj.uz

Submission #879803

# Submission time Handle Problem Language Result Execution time Memory
879803 2023-11-28T07:14:55 Z TAhmed33 Akcija (COCI21_akcija) C++
40 / 110
 299 ms 524288 KB 
#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 > 100) {
        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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 299 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 101972 KB Output is correct
2 Correct 36 ms 100436 KB Output is correct
3 Correct 32 ms 99420 KB Output is correct
4 Correct 31 ms 98900 KB Output is correct
5 Correct 42 ms 102228 KB Output is correct
6 Correct 21 ms 96740 KB Output is correct
7 Correct 25 ms 97884 KB Output is correct
8 Correct 23 ms 97116 KB Output is correct
9 Correct 22 ms 97116 KB Output is correct
10 Correct 21 ms 96608 KB Output is correct
11 Correct 21 ms 96536 KB Output is correct
12 Correct 21 ms 96612 KB Output is correct
13 Correct 32 ms 99428 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 115548 KB Output is correct
2 Correct 64 ms 116176 KB Output is correct
3 Correct 59 ms 112836 KB Output is correct
4 Correct 57 ms 112212 KB Output is correct
5 Correct 75 ms 116904 KB Output is correct
6 Correct 22 ms 97116 KB Output is correct
7 Correct 26 ms 98396 KB Output is correct
8 Correct 24 ms 97628 KB Output is correct
9 Correct 26 ms 98396 KB Output is correct
10 Correct 41 ms 105684 KB Output is correct
11 Correct 22 ms 96740 KB Output is correct
12 Correct 22 ms 96604 KB Output is correct
13 Correct 31 ms 100444 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -