oj.uz

Submission #530949

# Submission time Handle Problem Language Result Execution time Memory
530949 2022-02-27T07:49:16 Z Slavita Akcija (COCI21_akcija) C++14
70 / 110
 459 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];
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;
}
/*
*/

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 239 ms 319012 KB Output is correct
2 Correct 239 ms 324792 KB Output is correct
3 Correct 230 ms 309328 KB Output is correct
4 Correct 222 ms 310528 KB Output is correct
5 Correct 237 ms 323252 KB Output is correct
6 Correct 115 ms 233592 KB Output is correct
7 Correct 129 ms 234044 KB Output is correct
8 Correct 116 ms 233796 KB Output is correct
9 Correct 117 ms 235332 KB Output is correct
10 Correct 145 ms 253596 KB Output is correct
11 Correct 125 ms 233412 KB Output is correct
12 Correct 102 ms 233460 KB Output is correct
13 Correct 105 ms 233496 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 319012 KB Output is correct
2 Correct 239 ms 324792 KB Output is correct
3 Correct 230 ms 309328 KB Output is correct
4 Correct 222 ms 310528 KB Output is correct
5 Correct 237 ms 323252 KB Output is correct
6 Correct 115 ms 233592 KB Output is correct
7 Correct 129 ms 234044 KB Output is correct
8 Correct 116 ms 233796 KB Output is correct
9 Correct 117 ms 235332 KB Output is correct
10 Correct 145 ms 253596 KB Output is correct
11 Correct 125 ms 233412 KB Output is correct
12 Correct 102 ms 233460 KB Output is correct
13 Correct 105 ms 233496 KB Output is correct
14 Correct 340 ms 404292 KB Output is correct
15 Correct 340 ms 415948 KB Output is correct
16 Correct 317 ms 385036 KB Output is correct
17 Correct 298 ms 387556 KB Output is correct
18 Correct 390 ms 412912 KB Output is correct
19 Correct 114 ms 233632 KB Output is correct
20 Correct 141 ms 234460 KB Output is correct
21 Correct 130 ms 234016 KB Output is correct
22 Correct 121 ms 237124 KB Output is correct
23 Correct 164 ms 273752 KB Output is correct
24 Correct 101 ms 233400 KB Output is correct
25 Correct 126 ms 233384 KB Output is correct
26 Correct 103 ms 233508 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 459 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 246300 KB Output is correct
2 Correct 155 ms 247072 KB Output is correct
3 Correct 134 ms 243228 KB Output is correct
4 Correct 141 ms 240876 KB Output is correct
5 Correct 144 ms 248064 KB Output is correct
6 Correct 115 ms 233412 KB Output is correct
7 Correct 112 ms 236312 KB Output is correct
8 Correct 116 ms 234156 KB Output is correct
9 Correct 127 ms 234052 KB Output is correct
10 Correct 103 ms 233336 KB Output is correct
11 Correct 103 ms 233492 KB Output is correct
12 Correct 112 ms 233412 KB Output is correct
13 Correct 151 ms 242308 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 273780 KB Output is correct
2 Correct 211 ms 272412 KB Output is correct
3 Correct 186 ms 266288 KB Output is correct
4 Correct 195 ms 266084 KB Output is correct
5 Correct 211 ms 274112 KB Output is correct
6 Correct 102 ms 233636 KB Output is correct
7 Correct 111 ms 236924 KB Output is correct
8 Correct 110 ms 235024 KB Output is correct
9 Correct 112 ms 236592 KB Output is correct
10 Correct 129 ms 243664 KB Output is correct
11 Correct 107 ms 233436 KB Output is correct
12 Correct 104 ms 233372 KB Output is correct
13 Correct 156 ms 241096 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 319012 KB Output is correct
2 Correct 239 ms 324792 KB Output is correct
3 Correct 230 ms 309328 KB Output is correct
4 Correct 222 ms 310528 KB Output is correct
5 Correct 237 ms 323252 KB Output is correct
6 Correct 115 ms 233592 KB Output is correct
7 Correct 129 ms 234044 KB Output is correct
8 Correct 116 ms 233796 KB Output is correct
9 Correct 117 ms 235332 KB Output is correct
10 Correct 145 ms 253596 KB Output is correct
11 Correct 125 ms 233412 KB Output is correct
12 Correct 102 ms 233460 KB Output is correct
13 Correct 105 ms 233496 KB Output is correct
14 Correct 340 ms 404292 KB Output is correct
15 Correct 340 ms 415948 KB Output is correct
16 Correct 317 ms 385036 KB Output is correct
17 Correct 298 ms 387556 KB Output is correct
18 Correct 390 ms 412912 KB Output is correct
19 Correct 114 ms 233632 KB Output is correct
20 Correct 141 ms 234460 KB Output is correct
21 Correct 130 ms 234016 KB Output is correct
22 Correct 121 ms 237124 KB Output is correct
23 Correct 164 ms 273752 KB Output is correct
24 Correct 101 ms 233400 KB Output is correct
25 Correct 126 ms 233384 KB Output is correct
26 Correct 103 ms 233508 KB Output is correct
27 Runtime error 459 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -