oj.uz

Submission #530948

# Submission time Handle Problem Language Result Execution time Memory
530948 2022-02-27T07:47:45 Z Slavita Akcija (COCI21_akcija) C++14
70 / 110
 391 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++){
            int kol = 0;
            for (auto item : dp[i][j]){
                kol++;
                if (kol > k) break;
                dp[i + 1][j].insert(item);
            }

            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].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 221 ms 318956 KB Output is correct
2 Correct 233 ms 324824 KB Output is correct
3 Correct 216 ms 309400 KB Output is correct
4 Correct 212 ms 310560 KB Output is correct
5 Correct 229 ms 323356 KB Output is correct
6 Correct 120 ms 233856 KB Output is correct
7 Correct 122 ms 234052 KB Output is correct
8 Correct 115 ms 233820 KB Output is correct
9 Correct 117 ms 235384 KB Output is correct
10 Correct 153 ms 253744 KB Output is correct
11 Correct 102 ms 233412 KB Output is correct
12 Correct 101 ms 233444 KB Output is correct
13 Correct 100 ms 233412 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 318956 KB Output is correct
2 Correct 233 ms 324824 KB Output is correct
3 Correct 216 ms 309400 KB Output is correct
4 Correct 212 ms 310560 KB Output is correct
5 Correct 229 ms 323356 KB Output is correct
6 Correct 120 ms 233856 KB Output is correct
7 Correct 122 ms 234052 KB Output is correct
8 Correct 115 ms 233820 KB Output is correct
9 Correct 117 ms 235384 KB Output is correct
10 Correct 153 ms 253744 KB Output is correct
11 Correct 102 ms 233412 KB Output is correct
12 Correct 101 ms 233444 KB Output is correct
13 Correct 100 ms 233412 KB Output is correct
14 Correct 321 ms 404240 KB Output is correct
15 Correct 333 ms 415940 KB Output is correct
16 Correct 391 ms 385036 KB Output is correct
17 Correct 298 ms 387396 KB Output is correct
18 Correct 327 ms 413040 KB Output is correct
19 Correct 115 ms 233668 KB Output is correct
20 Correct 120 ms 234512 KB Output is correct
21 Correct 115 ms 234036 KB Output is correct
22 Correct 122 ms 237180 KB Output is correct
23 Correct 166 ms 273716 KB Output is correct
24 Correct 102 ms 233324 KB Output is correct
25 Correct 102 ms 233436 KB Output is correct
26 Correct 102 ms 233504 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 383 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 138 ms 246212 KB Output is correct
2 Correct 142 ms 247056 KB Output is correct
3 Correct 142 ms 243136 KB Output is correct
4 Correct 125 ms 240844 KB Output is correct
5 Correct 145 ms 248004 KB Output is correct
6 Correct 106 ms 233404 KB Output is correct
7 Correct 109 ms 236340 KB Output is correct
8 Correct 103 ms 234272 KB Output is correct
9 Correct 110 ms 234180 KB Output is correct
10 Correct 107 ms 233440 KB Output is correct
11 Correct 102 ms 233368 KB Output is correct
12 Correct 101 ms 233416 KB Output is correct
13 Correct 135 ms 242372 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 273732 KB Output is correct
2 Correct 196 ms 272456 KB Output is correct
3 Correct 184 ms 266372 KB Output is correct
4 Correct 192 ms 266016 KB Output is correct
5 Correct 205 ms 274012 KB Output is correct
6 Correct 104 ms 233540 KB Output is correct
7 Correct 113 ms 236916 KB Output is correct
8 Correct 111 ms 235032 KB Output is correct
9 Correct 110 ms 236632 KB Output is correct
10 Correct 127 ms 243552 KB Output is correct
11 Correct 104 ms 233356 KB Output is correct
12 Correct 107 ms 233412 KB Output is correct
13 Correct 121 ms 241080 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 318956 KB Output is correct
2 Correct 233 ms 324824 KB Output is correct
3 Correct 216 ms 309400 KB Output is correct
4 Correct 212 ms 310560 KB Output is correct
5 Correct 229 ms 323356 KB Output is correct
6 Correct 120 ms 233856 KB Output is correct
7 Correct 122 ms 234052 KB Output is correct
8 Correct 115 ms 233820 KB Output is correct
9 Correct 117 ms 235384 KB Output is correct
10 Correct 153 ms 253744 KB Output is correct
11 Correct 102 ms 233412 KB Output is correct
12 Correct 101 ms 233444 KB Output is correct
13 Correct 100 ms 233412 KB Output is correct
14 Correct 321 ms 404240 KB Output is correct
15 Correct 333 ms 415940 KB Output is correct
16 Correct 391 ms 385036 KB Output is correct
17 Correct 298 ms 387396 KB Output is correct
18 Correct 327 ms 413040 KB Output is correct
19 Correct 115 ms 233668 KB Output is correct
20 Correct 120 ms 234512 KB Output is correct
21 Correct 115 ms 234036 KB Output is correct
22 Correct 122 ms 237180 KB Output is correct
23 Correct 166 ms 273716 KB Output is correct
24 Correct 102 ms 233324 KB Output is correct
25 Correct 102 ms 233436 KB Output is correct
26 Correct 102 ms 233504 KB Output is correct
27 Runtime error 383 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -