oj.uz

Submission #298581

# Submission time Handle Problem Language Result Execution time Memory
298581 2020-09-13T08:52:27 Z BeanZ Ice Hockey World Championship (CEOI15_bobek) C++14
70 / 100
 1000 ms 82624 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;
        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];
                        }
                }
                mem[sum]++;
        }
        vector<pair<ll, ll>> val;
        for (auto j : mem){
                val.push_back({j.first, j.second});
        }
        for (int i = 1; i < val.size(); i++){
                val[i].second += val[i - 1].second;
                //cout << val[i].first << " " << val[i].second << endl;
        }
        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].first > res) h = mid - 1;
                        else l = mid + 1;
                }
                if (h >= 0) ans = ans + val[h].second;
        }
        cout << ans;
}
/*
*/

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for (int i = 1; i < val.size(); i++){
      |                         ~~^~~~~~~~~~~~
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 1 ms 384 KB Output is correct

Subtask #2
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 1 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 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct

Subtask #3
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 1 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 1 ms 512 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 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 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 #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1536 KB Output is correct
2 Correct 221 ms 15208 KB Output is correct
3 Execution timed out 1055 ms 37488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2168 KB Output is correct
2 Correct 54 ms 4732 KB Output is correct
3 Correct 163 ms 1400 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 26 ms 2688 KB Output is correct
7 Correct 39 ms 5624 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 9196 KB Output is correct
2 Correct 243 ms 10352 KB Output is correct
3 Correct 242 ms 10484 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 69 ms 504 KB Output is correct
6 Correct 289 ms 2168 KB Output is correct
7 Correct 249 ms 20972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 41648 KB Output is correct
2 Correct 55 ms 5628 KB Output is correct
3 Correct 23 ms 3068 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 606 ms 41704 KB Output is correct
7 Correct 38 ms 5628 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5624 KB Output is correct
2 Correct 290 ms 20972 KB Output is correct
3 Correct 21 ms 3068 KB Output is correct
4 Correct 20 ms 3068 KB Output is correct
5 Correct 83 ms 384 KB Output is correct
6 Correct 46 ms 5628 KB Output is correct
7 Execution timed out 1053 ms 82624 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 74356 KB Time limit exceeded
2 Halted 0 ms 0 KB -