#include "biscuits.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int K=60;
long long count_tastiness(long long x,vector<long long> a)
{
vector<pair<long long,long long>> t[61];
vector<long long> p[61];
int i;
while(a.size()<=K)
a.push_back(0);
if(a[0]<x)
{
t[0]={{0,0},{a[0]+1,1}};
p[0]={1,0};
}
else
{
t[0]={{0,0},{a[0]-x+1,1},{a[0]+1,1}};
p[0]={2,1,0};
}
for(i=1;i<K;i++)
{
vector<pair<long long,long long>> tmp;
for(auto v:t[i-1])
{
tmp.push_back({a[i]+(v.fi+1)/2,v.se});
if(a[i]-x+(v.fi+1)/2>0)
tmp.push_back({a[i]-x+(v.fi+1)/2,v.se});
}
tmp.push_back({0,0});
sort(tmp.begin(),tmp.end());
for(unsigned j=0;j<tmp.size();)
{
t[i].push_back({tmp[j].fi,0});
for(;j<tmp.size() && tmp[j].fi==t[i].back().fi;j++)
t[i].back().se+=tmp[j].se;
}
//cerr<<i<<"\n";
//for(auto v:t[i])
// cerr<<v.fi<<","<<v.se<<" ";
//cerr<<"\n";
p[i].resize(t[i].size());
p[i].back()=0;
for(int j=t[i].size()-2;j>=0;j--)
{
//cerr<<j<<" "<<p[i].size()<<" "<<t[i].size()<<"\n";
p[i][j]=p[i][j+1]+t[i][j+1].se;
}
}
return p[K-1][0];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
2 ms |
364 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
6 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
25884 KB |
Output is correct |
2 |
Correct |
177 ms |
11768 KB |
Output is correct |
3 |
Correct |
294 ms |
21176 KB |
Output is correct |
4 |
Correct |
10 ms |
620 KB |
Output is correct |
5 |
Correct |
9 ms |
620 KB |
Output is correct |
6 |
Correct |
18 ms |
748 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Execution timed out |
1102 ms |
128068 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1103 ms |
50412 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
2 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
2 ms |
364 KB |
Output is correct |
19 |
Correct |
4 ms |
384 KB |
Output is correct |
20 |
Correct |
7 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
6 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
93 ms |
25884 KB |
Output is correct |
25 |
Correct |
177 ms |
11768 KB |
Output is correct |
26 |
Correct |
294 ms |
21176 KB |
Output is correct |
27 |
Correct |
10 ms |
620 KB |
Output is correct |
28 |
Correct |
9 ms |
620 KB |
Output is correct |
29 |
Correct |
18 ms |
748 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Execution timed out |
1102 ms |
128068 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |