oj.uz

Submission #1070909

# Submission time Handle Problem Language Result Execution time Memory
1070909 2024-08-22T20:40:50 Z codexistent Ice Hockey World Championship (CEOI15_bobek) C++14
0 / 100
 1000 ms 22804 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 << (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 ptr = msa.size() - 1;
    FOR(i, 0, msb.size() - 1){
        while(ptr != -1 && msa[ptr] + msb[i] > c) ptr--;

        r += ptr + 1;
    }

    cout << r << endl;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:5:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
   57 |     FOR(i, 0, msb.size() - 1){
      |         ~~~~~~~~~~~~~~~~~~~~          
bobek.cpp:57:5: note: in expansion of macro 'FOR'
   57 |     FOR(i, 0, msb.size() - 1){
      |     ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Execution timed out 1092 ms 348 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Runtime error 1 ms 348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 440 KB Output is correct
7 Runtime error 1 ms 348 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2256 KB Output is correct
2 Correct 69 ms 5312 KB Output is correct
3 Correct 271 ms 21076 KB Output is correct
4 Correct 66 ms 5312 KB Output is correct
5 Correct 12 ms 1580 KB Output is correct
6 Correct 8 ms 1052 KB Output is correct
7 Execution timed out 1028 ms 344 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2888 KB Output is correct
2 Correct 24 ms 2372 KB Output is correct
3 Correct 118 ms 12316 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 984 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Runtime error 9 ms 436 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4232 KB Output is correct
2 Correct 110 ms 8344 KB Output is correct
3 Correct 116 ms 8372 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 86 ms 8632 KB Output is correct
6 Correct 251 ms 20956 KB Output is correct
7 Runtime error 50 ms 344 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 16688 KB Output is correct
2 Correct 26 ms 2308 KB Output is correct
3 Correct 10 ms 1052 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 1020 KB Output is correct
6 Correct 203 ms 16812 KB Output is correct
7 Runtime error 10 ms 344 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2256 KB Output is correct
2 Correct 68 ms 5560 KB Output is correct
3 Correct 8 ms 980 KB Output is correct
4 Correct 9 ms 984 KB Output is correct
5 Correct 67 ms 8112 KB Output is correct
6 Correct 26 ms 2256 KB Output is correct
7 Execution timed out 1090 ms 344 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 22804 KB Output is correct
2 Correct 25 ms 2256 KB Output is correct
3 Correct 7 ms 1068 KB Output is correct
4 Correct 292 ms 22792 KB Output is correct
5 Correct 113 ms 10696 KB Output is correct
6 Correct 21 ms 1488 KB Output is correct
7 Runtime error 17 ms 604 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -