oj.uz

Submission #298582

# Submission time Handle Problem Language Result Execution time Memory
298582 2020-09-13T08:58:25 Z BeanZ Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 561 ms 8688 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
ll a[N];
map<ll, ll> mem;
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.INP", "r")){
                freopen("A.INP", "r", stdin);
                freopen("A.OUT", "w", stdout);
        }
        ll n, k;
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
        ll mid = n / 2;
        ll rem = n - n / 2;
        vector<ll> val;
        for (int i = 0; i < (1 << mid); i++){
                ll sum = 0;
                for (int j = 0; j < mid; j++){
                        if (i & (1 << j)){
                                sum = sum + a[j];
                        }
                }
                val.push_back(sum);
        }
        sort(val.begin(), val.end());
        ll ans = 0;
        for (int i = 0; i < (1 << rem); i++){
                ll sum = 0;
                for (int j = 0; j < rem; j++){
                        if (i & (1 << j)){
                                sum = sum + a[mid + j];
                        }
                }
                if (sum > k) continue;
                ll l = 0, h = val.size() - 1;
                ll res = k - sum;
                while (l <= h){
                        ll mid = (l + h) >> 1;
                        if (val[mid] > res) h = mid - 1;
                        else l = mid + 1;
                }
                if (h >= 0) ans = ans + h + 1;
        }
        cout << ans;
}
/*
*/

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |                 freopen("A.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bobek.cpp:15:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   15 |                 freopen("A.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1024 KB Output is correct
2 Correct 112 ms 2640 KB Output is correct
3 Correct 550 ms 8676 KB Output is correct
4 Correct 104 ms 2680 KB Output is correct
5 Correct 16 ms 1024 KB Output is correct
6 Correct 8 ms 768 KB Output is correct
7 Correct 14 ms 1024 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1532 KB Output is correct
2 Correct 35 ms 1024 KB Output is correct
3 Correct 223 ms 4596 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 16 ms 1024 KB Output is correct
7 Correct 14 ms 1024 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1532 KB Output is correct
2 Correct 177 ms 2552 KB Output is correct
3 Correct 163 ms 2552 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 96 ms 2732 KB Output is correct
6 Correct 267 ms 8676 KB Output is correct
7 Correct 77 ms 2552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 4596 KB Output is correct
2 Correct 33 ms 1024 KB Output is correct
3 Correct 11 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 190 ms 4540 KB Output is correct
7 Correct 14 ms 1024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1024 KB Output is correct
2 Correct 102 ms 2552 KB Output is correct
3 Correct 10 ms 768 KB Output is correct
4 Correct 10 ms 768 KB Output is correct
5 Correct 113 ms 2552 KB Output is correct
6 Correct 22 ms 1024 KB Output is correct
7 Correct 239 ms 8668 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 8676 KB Output is correct
2 Correct 37 ms 1024 KB Output is correct
3 Correct 11 ms 768 KB Output is correct
4 Correct 561 ms 8688 KB Output is correct
5 Correct 134 ms 4596 KB Output is correct
6 Correct 15 ms 1024 KB Output is correct
7 Correct 28 ms 1532 KB Output is correct