oj.uz

Submission #530970

# Submission time Handle Problem Language Result Execution time Memory
530970 2022-02-27T08:35:28 Z Slavita Akcija (COCI21_akcija) C++14
70 / 110
 445 ms 524292 KB 
#include <bits/stdc++.h>
#pragma optimize("O3")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ve vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define si(v) (int)v.size()
#define en '\n'
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update>
//#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e3 + 228;
const int big = 1e9 + 228;
const ll llbig = 1e18 + 228;
//ordered_set os; // os.order_of_key(4), (*os.find_by_order(5))
int n, m, ans, k;
pair<ll, ll> a[N];
map<ll, bool> dp[N][N];

bool cmp(pair<ll, ll> a, pair<ll, ll> b){
    if (a.se <= b.se) return 1;
    return 0;
}

void upd(ll &a, ll b){
    if (a > b) {a = b;}
}

//#undef int
int main(){
    //#define int long long
    iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    stable_sort(a + 1, a + n + 1, cmp);

    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++){
        for (int j = 0; j <= n; j++){
            int kol = 0;
            for (auto item : dp[i][j]){
                kol++;
                if (kol > k) break;
                dp[i + 1][j][item.fi] = 1;
            }

            if (j + 1 <= a[i + 1].se) {
                kol = 0;
                for (auto item : dp[i][j]){
                    kol++;
                    if (kol > k) break;
                    dp[i + 1][j + 1][item.fi + a[i + 1].fi] = 1;
                }
            }
        }
    }

    set<pair<ll, ll>> ans;
    for (int j = 1; j <= n; j++) {
        for (auto item : dp[n][j]){
            ans.insert({-j, item.fi});
        }
    }

    int kol = 0;
    for (auto item : ans){
        kol++;
        if (kol > k) break;
        cout << -item.fi << ' ' << item.se << en;
    }

    if (kol <= k){
        for (int i = kol + 1; i <= k; i++) cout << 0 << ' ' << 0 << en;
    }
    return 0;
}
/*
*/

Compilation message

Main.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("O3")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 347436 KB Output is correct
2 Correct 242 ms 355104 KB Output is correct
3 Correct 246 ms 334640 KB Output is correct
4 Correct 221 ms 336080 KB Output is correct
5 Correct 300 ms 353188 KB Output is correct
6 Correct 126 ms 233704 KB Output is correct
7 Correct 116 ms 234200 KB Output is correct
8 Correct 116 ms 233916 KB Output is correct
9 Correct 116 ms 235976 KB Output is correct
10 Correct 144 ms 260376 KB Output is correct
11 Correct 107 ms 233440 KB Output is correct
12 Correct 101 ms 233412 KB Output is correct
13 Correct 101 ms 233428 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 347436 KB Output is correct
2 Correct 242 ms 355104 KB Output is correct
3 Correct 246 ms 334640 KB Output is correct
4 Correct 221 ms 336080 KB Output is correct
5 Correct 300 ms 353188 KB Output is correct
6 Correct 126 ms 233704 KB Output is correct
7 Correct 116 ms 234200 KB Output is correct
8 Correct 116 ms 233916 KB Output is correct
9 Correct 116 ms 235976 KB Output is correct
10 Correct 144 ms 260376 KB Output is correct
11 Correct 107 ms 233440 KB Output is correct
12 Correct 101 ms 233412 KB Output is correct
13 Correct 101 ms 233428 KB Output is correct
14 Correct 367 ms 461172 KB Output is correct
15 Correct 380 ms 476728 KB Output is correct
16 Correct 348 ms 435508 KB Output is correct
17 Correct 323 ms 438704 KB Output is correct
18 Correct 445 ms 472732 KB Output is correct
19 Correct 111 ms 233724 KB Output is correct
20 Correct 119 ms 234824 KB Output is correct
21 Correct 121 ms 234180 KB Output is correct
22 Correct 117 ms 238368 KB Output is correct
23 Correct 172 ms 287148 KB Output is correct
24 Correct 100 ms 233332 KB Output is correct
25 Correct 99 ms 233412 KB Output is correct
26 Correct 106 ms 233528 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 524292 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 143 ms 249644 KB Output is correct
2 Correct 237 ms 250764 KB Output is correct
3 Correct 132 ms 245632 KB Output is correct
4 Correct 136 ms 242640 KB Output is correct
5 Correct 157 ms 251928 KB Output is correct
6 Correct 100 ms 233424 KB Output is correct
7 Correct 114 ms 237108 KB Output is correct
8 Correct 104 ms 234376 KB Output is correct
9 Correct 107 ms 234228 KB Output is correct
10 Correct 107 ms 233420 KB Output is correct
11 Correct 104 ms 233444 KB Output is correct
12 Correct 112 ms 233444 KB Output is correct
13 Correct 142 ms 244616 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 286840 KB Output is correct
2 Correct 227 ms 285056 KB Output is correct
3 Correct 201 ms 277032 KB Output is correct
4 Correct 204 ms 276652 KB Output is correct
5 Correct 225 ms 287184 KB Output is correct
6 Correct 103 ms 233596 KB Output is correct
7 Correct 116 ms 238052 KB Output is correct
8 Correct 108 ms 235588 KB Output is correct
9 Correct 117 ms 237600 KB Output is correct
10 Correct 134 ms 246832 KB Output is correct
11 Correct 101 ms 233428 KB Output is correct
12 Correct 103 ms 233340 KB Output is correct
13 Correct 127 ms 243508 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 347436 KB Output is correct
2 Correct 242 ms 355104 KB Output is correct
3 Correct 246 ms 334640 KB Output is correct
4 Correct 221 ms 336080 KB Output is correct
5 Correct 300 ms 353188 KB Output is correct
6 Correct 126 ms 233704 KB Output is correct
7 Correct 116 ms 234200 KB Output is correct
8 Correct 116 ms 233916 KB Output is correct
9 Correct 116 ms 235976 KB Output is correct
10 Correct 144 ms 260376 KB Output is correct
11 Correct 107 ms 233440 KB Output is correct
12 Correct 101 ms 233412 KB Output is correct
13 Correct 101 ms 233428 KB Output is correct
14 Correct 367 ms 461172 KB Output is correct
15 Correct 380 ms 476728 KB Output is correct
16 Correct 348 ms 435508 KB Output is correct
17 Correct 323 ms 438704 KB Output is correct
18 Correct 445 ms 472732 KB Output is correct
19 Correct 111 ms 233724 KB Output is correct
20 Correct 119 ms 234824 KB Output is correct
21 Correct 121 ms 234180 KB Output is correct
22 Correct 117 ms 238368 KB Output is correct
23 Correct 172 ms 287148 KB Output is correct
24 Correct 100 ms 233332 KB Output is correct
25 Correct 99 ms 233412 KB Output is correct
26 Correct 106 ms 233528 KB Output is correct
27 Runtime error 427 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -