oj.uz

Submission #530947

# Submission time Handle Problem Language Result Execution time Memory
530947 2022-02-27T07:46:19 Z Slavita Akcija (COCI21_akcija) C++14
20 / 110
 1461 ms 524292 KB 
#include <bits/stdc++.h>
//#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];
set<ll> 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].insert(0);
    for (int i = 0; i < n; i++){
        for (int j = 0; j <= n; j++){
            for (auto item : dp[i][j]){
                dp[i + 1][j].insert(item);
            }

            if (j + 1 <= a[i + 1].se) {
                for (auto item : dp[i][j]){
                    dp[i + 1][j + 1].insert(item + a[i + 1].fi);
                }
            }
        }
    }
    set<pair<ll, ll>> ans;
    for (int j = 1; j <= n; j++) {
        for (auto item : dp[n][j]){
            ans.insert({-j, item});
        }
    }
    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;
}
/*
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 318992 KB Output is correct
2 Correct 260 ms 324692 KB Output is correct
3 Correct 251 ms 309376 KB Output is correct
4 Correct 238 ms 310476 KB Output is correct
5 Correct 260 ms 323296 KB Output is correct
6 Correct 132 ms 233640 KB Output is correct
7 Correct 152 ms 233936 KB Output is correct
8 Correct 139 ms 233760 KB Output is correct
9 Correct 157 ms 235384 KB Output is correct
10 Correct 164 ms 253636 KB Output is correct
11 Correct 115 ms 233440 KB Output is correct
12 Correct 109 ms 233420 KB Output is correct
13 Correct 113 ms 233516 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 318992 KB Output is correct
2 Correct 260 ms 324692 KB Output is correct
3 Correct 251 ms 309376 KB Output is correct
4 Correct 238 ms 310476 KB Output is correct
5 Correct 260 ms 323296 KB Output is correct
6 Correct 132 ms 233640 KB Output is correct
7 Correct 152 ms 233936 KB Output is correct
8 Correct 139 ms 233760 KB Output is correct
9 Correct 157 ms 235384 KB Output is correct
10 Correct 164 ms 253636 KB Output is correct
11 Correct 115 ms 233440 KB Output is correct
12 Correct 109 ms 233420 KB Output is correct
13 Correct 113 ms 233516 KB Output is correct
14 Runtime error 1363 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1461 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 472 ms 315428 KB Output is correct
2 Correct 790 ms 378928 KB Output is correct
3 Correct 270 ms 272696 KB Output is correct
4 Correct 210 ms 252024 KB Output is correct
5 Correct 654 ms 356508 KB Output is correct
6 Correct 151 ms 233352 KB Output is correct
7 Correct 133 ms 238620 KB Output is correct
8 Correct 111 ms 234176 KB Output is correct
9 Correct 128 ms 233976 KB Output is correct
10 Correct 107 ms 233376 KB Output is correct
11 Correct 119 ms 233444 KB Output is correct
12 Correct 106 ms 233416 KB Output is correct
13 Correct 232 ms 266736 KB Output is correct

Subtask #5
0 / 30.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 318992 KB Output is correct
2 Correct 260 ms 324692 KB Output is correct
3 Correct 251 ms 309376 KB Output is correct
4 Correct 238 ms 310476 KB Output is correct
5 Correct 260 ms 323296 KB Output is correct
6 Correct 132 ms 233640 KB Output is correct
7 Correct 152 ms 233936 KB Output is correct
8 Correct 139 ms 233760 KB Output is correct
9 Correct 157 ms 235384 KB Output is correct
10 Correct 164 ms 253636 KB Output is correct
11 Correct 115 ms 233440 KB Output is correct
12 Correct 109 ms 233420 KB Output is correct
13 Correct 113 ms 233516 KB Output is correct
14 Runtime error 1363 ms 524292 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -