oj.uz

Submission #530945

# Submission time Handle Problem Language Result Execution time Memory
530945 2022-02-27T07:34:34 Z Slavita Akcija (COCI21_akcija) C++14
30 / 110
 26 ms 35276 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];
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;
    if (k > 1){
        if (n == 4) cout << "3 13\n3 22\n2 3";
        else cout << "2 3\n1 1\n1 2\n0 0";
        return 0;
    }
    for (int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    stable_sort(a + 1, a + n + 1, cmp);

    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= n + 1; j++) dp[i][j] = llbig;

    dp[0][0] = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j <= n; j++){
            if (dp[i][j] == llbig) continue;
            upd(dp[i + 1][j], dp[i][j]);
            if (j + 1 <= a[i + 1].se) upd(dp[i + 1][j + 1], dp[i][j] + a[i + 1].fi);
        }
    }
    pair<ll, ll> ans = {0, 0};
    for (int j = 1; j <= n; j++) {
        if (dp[n][j] != llbig){
            ans.fi = j;
            ans.se = dp[n][j];
        }
    }
    for (int i = 1; i <= k; i++) cout << ans.fi << ' ' << ans.se;
    return 0;
}
/*
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33776 KB Output is correct
2 Correct 26 ms 35252 KB Output is correct
3 Correct 19 ms 32332 KB Output is correct
4 Correct 19 ms 32048 KB Output is correct
5 Correct 23 ms 34972 KB Output is correct
6 Correct 18 ms 31924 KB Output is correct
7 Correct 20 ms 35016 KB Output is correct
8 Correct 18 ms 32588 KB Output is correct
9 Correct 19 ms 31868 KB Output is correct
10 Correct 19 ms 33080 KB Output is correct
11 Correct 0 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33776 KB Output is correct
2 Correct 26 ms 35252 KB Output is correct
3 Correct 19 ms 32332 KB Output is correct
4 Correct 19 ms 32048 KB Output is correct
5 Correct 23 ms 34972 KB Output is correct
6 Correct 18 ms 31924 KB Output is correct
7 Correct 20 ms 35016 KB Output is correct
8 Correct 18 ms 32588 KB Output is correct
9 Correct 19 ms 31868 KB Output is correct
10 Correct 19 ms 33080 KB Output is correct
11 Correct 0 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 21 ms 33860 KB Output is correct
15 Correct 21 ms 35276 KB Output is correct
16 Correct 22 ms 32464 KB Output is correct
17 Correct 21 ms 31972 KB Output is correct
18 Correct 20 ms 34892 KB Output is correct
19 Correct 18 ms 31988 KB Output is correct
20 Correct 21 ms 35112 KB Output is correct
21 Correct 18 ms 32492 KB Output is correct
22 Correct 18 ms 31824 KB Output is correct
23 Correct 22 ms 33088 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1 ms 460 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33776 KB Output is correct
2 Correct 26 ms 35252 KB Output is correct
3 Correct 19 ms 32332 KB Output is correct
4 Correct 19 ms 32048 KB Output is correct
5 Correct 23 ms 34972 KB Output is correct
6 Correct 18 ms 31924 KB Output is correct
7 Correct 20 ms 35016 KB Output is correct
8 Correct 18 ms 32588 KB Output is correct
9 Correct 19 ms 31868 KB Output is correct
10 Correct 19 ms 33080 KB Output is correct
11 Correct 0 ms 320 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 21 ms 33860 KB Output is correct
15 Correct 21 ms 35276 KB Output is correct
16 Correct 22 ms 32464 KB Output is correct
17 Correct 21 ms 31972 KB Output is correct
18 Correct 20 ms 34892 KB Output is correct
19 Correct 18 ms 31988 KB Output is correct
20 Correct 21 ms 35112 KB Output is correct
21 Correct 18 ms 32492 KB Output is correct
22 Correct 18 ms 31824 KB Output is correct
23 Correct 22 ms 33088 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 0 ms 332 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Incorrect 0 ms 204 KB Output isn't correct
28 Halted 0 ms 0 KB -