oj.uz

Submission #767918

# Submission time Handle Problem Language Result Execution time Memory
767918 2023-06-27T09:32:40 Z dxz05 Akcija (COCI21_akcija) C++17
40 / 110
 167 ms 31700 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
#define BIT(x, i) (((x) >> (i)) & 1)
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2002;

pair<int, int> p[N];
ll dp[N][N];

void solve(){
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) cin >> p[i].first >> p[i].second;

    sort(p + 1, p + n + 1, [](auto x, auto y) {
        return x.second < y.second;
    });

    if (k == 1) {
        for (int i = 0; i <= n; i++) {
            for (int t = 1; t <= n; t++) {
                dp[i][t] = 1e18;
            }
        }

        for (int i = 1; i <= n; i++) {
            auto [w, d] = p[i];

            for (int t = 0; t <= i; t++) {
                if (d > t) {
                    dp[i][t + 1] = min(dp[i - 1][t + 1], dp[i - 1][t] + w);
                }
            }
        }

        for (int t = n; t >= 1; t--) {
            ll ans = 1e18;
            for (int i = t; i <= n; i++) {
                ans = min(ans, dp[i][t]);
            }
            if (ans != 1e18) {
                cout << t << ' ' << ans << endl;
                return;
            }
        }
    }

    assert(n <= 20);

    vector<pair<int, ll>> v;

    for (int mask = 0; mask < (1 << n); mask++){
        int ok = 1, cnt = 0;
        ll tot = 0;
        for (int i = 1; i <= n; i++){
            if (!BIT(mask, i - 1)) continue;

            if (p[i].second <= cnt){
                ok = 0;
            } else {
                cnt++;
                tot += p[i].first;
            }

        }

        if (ok) v.emplace_back(cnt, -tot);
    }

    sort(rall(v));

    v.resize(k);

    for (auto [x, y] : v) cout << x << ' ' << -y << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:92:13: warning: unused variable 'startTime' [-Wunused-variable]
   92 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30420 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Correct 13 ms 29076 KB Output is correct
4 Correct 13 ms 28816 KB Output is correct
5 Correct 14 ms 31316 KB Output is correct
6 Correct 16 ms 28748 KB Output is correct
7 Correct 20 ms 31496 KB Output is correct
8 Correct 17 ms 29288 KB Output is correct
9 Correct 17 ms 28504 KB Output is correct
10 Correct 15 ms 29640 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30420 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Correct 13 ms 29076 KB Output is correct
4 Correct 13 ms 28816 KB Output is correct
5 Correct 14 ms 31316 KB Output is correct
6 Correct 16 ms 28748 KB Output is correct
7 Correct 20 ms 31496 KB Output is correct
8 Correct 17 ms 29288 KB Output is correct
9 Correct 17 ms 28504 KB Output is correct
10 Correct 15 ms 29640 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 16 ms 30396 KB Output is correct
15 Correct 15 ms 31700 KB Output is correct
16 Correct 14 ms 29136 KB Output is correct
17 Correct 13 ms 28756 KB Output is correct
18 Correct 15 ms 31424 KB Output is correct
19 Correct 16 ms 28768 KB Output is correct
20 Correct 22 ms 31448 KB Output is correct
21 Correct 17 ms 29304 KB Output is correct
22 Correct 16 ms 28624 KB Output is correct
23 Correct 15 ms 29648 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 8720 KB Output is correct
2 Correct 167 ms 16816 KB Output is correct
3 Correct 42 ms 4548 KB Output is correct
4 Correct 34 ms 2476 KB Output is correct
5 Correct 154 ms 16776 KB Output is correct
6 Correct 18 ms 340 KB Output is correct
7 Correct 84 ms 912 KB Output is correct
8 Correct 21 ms 548 KB Output is correct
9 Correct 23 ms 452 KB Output is correct
10 Correct 35 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 54 ms 4556 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30420 KB Output is correct
2 Correct 14 ms 31700 KB Output is correct
3 Correct 13 ms 29076 KB Output is correct
4 Correct 13 ms 28816 KB Output is correct
5 Correct 14 ms 31316 KB Output is correct
6 Correct 16 ms 28748 KB Output is correct
7 Correct 20 ms 31496 KB Output is correct
8 Correct 17 ms 29288 KB Output is correct
9 Correct 17 ms 28504 KB Output is correct
10 Correct 15 ms 29640 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 16 ms 30396 KB Output is correct
15 Correct 15 ms 31700 KB Output is correct
16 Correct 14 ms 29136 KB Output is correct
17 Correct 13 ms 28756 KB Output is correct
18 Correct 15 ms 31424 KB Output is correct
19 Correct 16 ms 28768 KB Output is correct
20 Correct 22 ms 31448 KB Output is correct
21 Correct 17 ms 29304 KB Output is correct
22 Correct 16 ms 28624 KB Output is correct
23 Correct 15 ms 29648 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Runtime error 2 ms 476 KB Execution killed with signal 6
28 Halted 0 ms 0 KB -