oj.uz

Submission #72411

# Submission time Handle Problem Language Result Execution time Memory
72411 2018-08-26T07:51:04 Z someone_aa Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 571 ms 21500 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 42;
vector<ll>suma, sumb;
ll arr[maxn], n, fn, sn;
ll budget;

void get_f() {
    for(int i=0;i<(1<<fn);i++) {
        ll sum = 0LL;
        for(int j=0;j<fn;j++) {
            if(i&(1<<j)) {
                sum += arr[j];
            }
        }
        suma.pb(sum);
    }
    sort(suma.begin(), suma.end());
}

void get_s() {
    for(int i=0;i<(1<<sn);i++) {
        ll sum = 0LL;
        for(int j=0;j<sn;j++) {
            if(i&(1<<j)) {
                sum += arr[j+fn];
            }
        }
        sumb.pb(sum);
    }
    sort(sumb.begin(), sumb.end());
}

void solve() {
    ll result = 0LL;
    for(int i=0;i<suma.size();i++) {
        if(suma[i] > budget) continue;
        else {
            int ind = 0;
            for(int cekor = sumb.size()/2;cekor>0;cekor/=2) {
                while(ind + cekor < sumb.size() && sumb[ind+cekor]<=(budget-suma[i])) ind += cekor;
            }
            result += 1LL * (ind+1);
        }
    }
    cout<<result;
}

int main() {

    cin>>n>>budget;
    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    fn = n / 2;
    sn = n - fn;
    get_f();
    get_s();
    solve();
    return 0;
}

Compilation message

bobek.cpp: In function 'void solve()':
bobek.cpp:39:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<suma.size();i++) {
                 ~^~~~~~~~~~~~
bobek.cpp:44:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(ind + cekor < sumb.size() && sumb[ind+cekor]<=(budget-suma[i])) ind += cekor;
                       ~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 356 KB Output is correct
2 Correct 3 ms 560 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2460 KB Output is correct
2 Correct 128 ms 5928 KB Output is correct
3 Correct 533 ms 21248 KB Output is correct
4 Correct 128 ms 21248 KB Output is correct
5 Correct 23 ms 21248 KB Output is correct
6 Correct 15 ms 21248 KB Output is correct
7 Correct 27 ms 21248 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 21248 KB Output is correct
2 Correct 40 ms 21248 KB Output is correct
3 Correct 218 ms 21248 KB Output is correct
4 Correct 3 ms 21248 KB Output is correct
5 Correct 16 ms 21248 KB Output is correct
6 Correct 25 ms 21248 KB Output is correct
7 Correct 22 ms 21248 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21248 KB Output is correct
2 Correct 182 ms 21248 KB Output is correct
3 Correct 166 ms 21248 KB Output is correct
4 Correct 2 ms 21248 KB Output is correct
5 Correct 128 ms 21248 KB Output is correct
6 Correct 424 ms 21496 KB Output is correct
7 Correct 162 ms 21496 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 21496 KB Output is correct
2 Correct 43 ms 21496 KB Output is correct
3 Correct 15 ms 21496 KB Output is correct
4 Correct 2 ms 21496 KB Output is correct
5 Correct 12 ms 21496 KB Output is correct
6 Correct 347 ms 21496 KB Output is correct
7 Correct 23 ms 21496 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 21496 KB Output is correct
2 Correct 135 ms 21496 KB Output is correct
3 Correct 14 ms 21496 KB Output is correct
4 Correct 15 ms 21496 KB Output is correct
5 Correct 131 ms 21496 KB Output is correct
6 Correct 38 ms 21496 KB Output is correct
7 Correct 409 ms 21496 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 21500 KB Output is correct
2 Correct 41 ms 21500 KB Output is correct
3 Correct 16 ms 21500 KB Output is correct
4 Correct 571 ms 21500 KB Output is correct
5 Correct 174 ms 21500 KB Output is correct
6 Correct 27 ms 21500 KB Output is correct
7 Correct 48 ms 21500 KB Output is correct