oj.uz

Submission #1070926

# Submission time Handle Problem Language Result Execution time Memory
1070926 2024-08-22T20:57:42 Z codexistent Ice Hockey World Championship (CEOI15_bobek) C++14
90 / 100
 267 ms 22592 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 45
#define FOR(i, a, b) for(ll i = a; i <= b; i++)

ll n, c, m[MAXN], r = 1;

int main(){
    cin >> n >> c;
    FOR(i, 1, n) cin >> m[i];
    sort(m + 1, m + 1 + n);

    if(n == 1) {
        cout << (1 + m[1] <= c) << endl;
        return 0;
    }

    pair<ll, ll> a = {1, (1 + n) / 2}, b = {(1 + n) / 2 + 1, n};

    // solve first half
    ll mska = pow(2, a.second - a.first + 1);
    vector<ll> msa;
    FOR(msk, 1, mska - 1){
        ll s = 0;
        FOR(i, a.first, a.second){
            if(msk & (1 << (i - a.first))){
                s += m[i];
            }
        }

        if(s > c) continue;
        r++;
        msa.push_back(s);
    }
    sort(begin(msa), end(msa));

    // solve second half
    ll mskb = pow(2, b.second - b.first + 1);
    vector<ll> msb;
    FOR(msk, 1, mskb - 1){
        ll s = 0;
        FOR(i, b.first, b.second){
            if(msk & (1 << (i - b.first))){
                s += m[i];
            }
        }

        if(s > c) continue;
        r++;
        msb.push_back(s);
    }
    sort(begin(msb), end(msb));

    // combine both halves
    ll na = (ll)msa.size(), nb = (ll)msb.size();

    ll ptr = na - 1;
    FOR(i, 0, nb - 1){
        while(ptr >= 0 && msa[ptr] + msb[i] > c) {
            ptr--;
        }

        r += ptr + 1;
    }

    cout << r << endl;
}

/*
8 1232
143 321241 53 1532 123 3253 32513 1232
*/

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2492 KB Output is correct
2 Correct 62 ms 5316 KB Output is correct
3 Correct 257 ms 21832 KB Output is correct
4 Correct 62 ms 5316 KB Output is correct
5 Correct 11 ms 1492 KB Output is correct
6 Correct 7 ms 980 KB Output is correct
7 Correct 8 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2768 KB Output is correct
2 Correct 23 ms 2256 KB Output is correct
3 Correct 112 ms 12164 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 5 ms 984 KB Output is correct
6 Correct 16 ms 1608 KB Output is correct
7 Correct 8 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4288 KB Output is correct
2 Correct 102 ms 8376 KB Output is correct
3 Correct 94 ms 8236 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 73 ms 8628 KB Output is correct
6 Correct 249 ms 22188 KB Output is correct
7 Correct 48 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 16672 KB Output is correct
2 Correct 24 ms 2256 KB Output is correct
3 Correct 8 ms 984 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 984 KB Output is correct
6 Correct 211 ms 16820 KB Output is correct
7 Correct 8 ms 344 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2256 KB Output is correct
2 Correct 63 ms 5308 KB Output is correct
3 Correct 7 ms 980 KB Output is correct
4 Correct 7 ms 1040 KB Output is correct
5 Correct 69 ms 8120 KB Output is correct
6 Correct 23 ms 2252 KB Output is correct
7 Correct 123 ms 408 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 21756 KB Output is correct
2 Correct 23 ms 2256 KB Output is correct
3 Correct 8 ms 980 KB Output is correct
4 Correct 260 ms 22592 KB Output is correct
5 Correct 96 ms 11188 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Correct 16 ms 432 KB Output is correct