oj.uz

Submission #767880

# Submission time Handle Problem Language Result Execution time Memory
767880 2023-06-27T08:53:42 Z dxz05 Akcija (COCI21_akcija) C++17
10 / 110
 218 ms 49644 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 = 1e6 + 3e2;

pair<int, int> p[N];
multiset<pair<int, ll>> best[N];

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

    function<void(int, int, ll)> add = [&](int i, int x, ll y){
        y = -y;
        if (best[i].size() < k){
            best[i].emplace(x, y);
        } else if (*best[i].begin() < MP(x, y)){
            best[i].erase(best[i].begin());
            best[i].emplace(x, y);
        }
    };

    add(0, 0, 0);

    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;
    });

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

        for (int j = 0; j < i; j++) {
            multiset<pair<int, ll>> s = best[j];
            for (auto [x, y]: s) {
                y = -y;
                if (x < d) add(i, x + 1, y + w);
            }
        }
    }

    multiset<pair<int, ll>> s;
    for (int i = 0; i <= n; i++){
        s.insert(all(best[i]));
    }

    for (auto it = s.rbegin(); it != s.rend(); it++){
        if (k-- == 0) break;
        cout << it->first << ' ' << -it->second << 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 lambda function:
Main.cpp:28:28: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |         if (best[i].size() < k){
      |             ~~~~~~~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:68:13: warning: unused variable 'startTime' [-Wunused-variable]
   68 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 47428 KB Output is correct
2 Correct 119 ms 47484 KB Output is correct
3 Correct 121 ms 47456 KB Output is correct
4 Correct 111 ms 47436 KB Output is correct
5 Correct 123 ms 47492 KB Output is correct
6 Correct 55 ms 47512 KB Output is correct
7 Correct 62 ms 47528 KB Output is correct
8 Correct 67 ms 47528 KB Output is correct
9 Correct 68 ms 47416 KB Output is correct
10 Correct 76 ms 47584 KB Output is correct
11 Correct 23 ms 47188 KB Output is correct
12 Correct 28 ms 47188 KB Output is correct
13 Correct 23 ms 47240 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 47428 KB Output is correct
2 Correct 119 ms 47484 KB Output is correct
3 Correct 121 ms 47456 KB Output is correct
4 Correct 111 ms 47436 KB Output is correct
5 Correct 123 ms 47492 KB Output is correct
6 Correct 55 ms 47512 KB Output is correct
7 Correct 62 ms 47528 KB Output is correct
8 Correct 67 ms 47528 KB Output is correct
9 Correct 68 ms 47416 KB Output is correct
10 Correct 76 ms 47584 KB Output is correct
11 Correct 23 ms 47188 KB Output is correct
12 Correct 28 ms 47188 KB Output is correct
13 Correct 23 ms 47240 KB Output is correct
14 Incorrect 118 ms 47504 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 47676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 49412 KB Output is correct
2 Correct 40 ms 49604 KB Output is correct
3 Correct 35 ms 49236 KB Output is correct
4 Correct 33 ms 48912 KB Output is correct
5 Correct 40 ms 49644 KB Output is correct
6 Correct 23 ms 47228 KB Output is correct
7 Incorrect 32 ms 49172 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 48332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 47428 KB Output is correct
2 Correct 119 ms 47484 KB Output is correct
3 Correct 121 ms 47456 KB Output is correct
4 Correct 111 ms 47436 KB Output is correct
5 Correct 123 ms 47492 KB Output is correct
6 Correct 55 ms 47512 KB Output is correct
7 Correct 62 ms 47528 KB Output is correct
8 Correct 67 ms 47528 KB Output is correct
9 Correct 68 ms 47416 KB Output is correct
10 Correct 76 ms 47584 KB Output is correct
11 Correct 23 ms 47188 KB Output is correct
12 Correct 28 ms 47188 KB Output is correct
13 Correct 23 ms 47240 KB Output is correct
14 Incorrect 118 ms 47504 KB Output isn't correct
15 Halted 0 ms 0 KB -