Submission #1070927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1070927	2024-08-22T20:58:06 Z	codexistent	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	271 ms	22336 KB

bobek

#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
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	344 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	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	1 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	0 ms	348 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	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 #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2260 KB	Output is correct
2	Correct	65 ms	5428 KB	Output is correct
3	Correct	258 ms	21680 KB	Output is correct
4	Correct	65 ms	5312 KB	Output is correct
5	Correct	12 ms	1596 KB	Output is correct
6	Correct	8 ms	984 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	33 ms	2764 KB	Output is correct
2	Correct	24 ms	2256 KB	Output is correct
3	Correct	118 ms	12212 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	6 ms	984 KB	Output is correct
6	Correct	16 ms	1688 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	48 ms	4208 KB	Output is correct
2	Correct	97 ms	8516 KB	Output is correct
3	Correct	95 ms	8376 KB	Output is correct
4	Correct	0 ms	600 KB	Output is correct
5	Correct	71 ms	8632 KB	Output is correct
6	Correct	237 ms	22172 KB	Output is correct
7	Correct	49 ms	348 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	200 ms	16560 KB	Output is correct
2	Correct	25 ms	2256 KB	Output is correct
3	Correct	7 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	209 ms	16812 KB	Output is correct
7	Correct	9 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	66 ms	5312 KB	Output is correct
3	Correct	7 ms	980 KB	Output is correct
4	Correct	7 ms	1044 KB	Output is correct
5	Correct	81 ms	8132 KB	Output is correct
6	Correct	25 ms	2256 KB	Output is correct
7	Correct	124 ms	412 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	271 ms	22336 KB	Output is correct
2	Correct	24 ms	2256 KB	Output is correct
3	Correct	8 ms	984 KB	Output is correct
4	Correct	268 ms	21028 KB	Output is correct
5	Correct	98 ms	11188 KB	Output is correct
6	Correct	16 ms	1492 KB	Output is correct
7	Correct	16 ms	348 KB	Output is correct

Submission #1070927

Compilation message