#include<bits/stdc++.h>
#include "biscuits.h"
using namespace std;
using ll = long long;
ll INF = 1e18;
ll count_tastiness(ll x, vector<ll> a) {
if(x == 1){
ll ans = 1;
priority_queue<pair<ll, ll>> pq;
for(int i=a.size()-1;i>=0;i--){
ll u = 1ll << i;
if(a[i]){
ll p = 0;
queue<pair<ll, ll>> q;
while(!pq.empty() && pq.top().first > u){
auto [x, y] = pq.top(); pq.pop();
ll s = min(x / u - 1, a[i]);
p += s * y;
ans += s * y;
if(x > u * s) q.push({x - u * s, y});
else p += y;
}
while(!q.empty()) pq.push(q.front()), q.pop();
ans += a[i];
pq.push({u, a[i] + p});
}
}
return ans;
}
ll ans = 0, sum = 0;
for(int i=0;i<a.size();i++) sum += (1ll << i) * a[i];
ll mx = sum / x;
while((1ll << a.size()) < mx) a.push_back(0);
queue<ll> qu, qc, ql;
qu.push(0), qc.push(0), ql.push(0), ans++;
set<pair<ll, ll>> s;
while(!qu.empty()){
ll u = qu.front(), c = qc.front(), l = ql.front() / 2 + a[c]; qu.pop(), qc.pop(), ql.pop();
if(u + (1ll << c) > mx || s.count({u, c})) continue;
s.insert({u, c});
qu.push(u), qc.push(c + 1), ql.push(l);
if(l >= x) qu.push(u + (1ll << c)), qc.push(c + 1), ql.push(l - x), ans++;
}
return ans;
}
Compilation message
biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<a.size();i++) sum += (1ll << i) * a[i];
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
33 ms |
1664 KB |
Output is correct |
5 |
Correct |
9 ms |
1408 KB |
Output is correct |
6 |
Correct |
60 ms |
3192 KB |
Output is correct |
7 |
Correct |
3 ms |
544 KB |
Output is correct |
8 |
Correct |
60 ms |
3192 KB |
Output is correct |
9 |
Correct |
12 ms |
1280 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
58 ms |
1792 KB |
Output is correct |
13 |
Correct |
24 ms |
948 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
0 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
256 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1093 ms |
122816 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1089 ms |
15780 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
33 ms |
1664 KB |
Output is correct |
5 |
Correct |
9 ms |
1408 KB |
Output is correct |
6 |
Correct |
60 ms |
3192 KB |
Output is correct |
7 |
Correct |
3 ms |
544 KB |
Output is correct |
8 |
Correct |
60 ms |
3192 KB |
Output is correct |
9 |
Correct |
12 ms |
1280 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
58 ms |
1792 KB |
Output is correct |
13 |
Correct |
24 ms |
948 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
1 ms |
256 KB |
Output is correct |
17 |
Correct |
0 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
256 KB |
Output is correct |
20 |
Correct |
2 ms |
256 KB |
Output is correct |
21 |
Correct |
0 ms |
256 KB |
Output is correct |
22 |
Correct |
1 ms |
256 KB |
Output is correct |
23 |
Correct |
1 ms |
256 KB |
Output is correct |
24 |
Execution timed out |
1093 ms |
122816 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |