#include "biscuits.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include <cstdint>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
int lg=60;
long long count_tastiness(long long x, vector<ll>v) {
int sum;
if(x<=10000){
int k=v.size();
k++;
vector<int>nv(k,0);
k=nv.size();
for(int i=0;i<k-1;i++){
if(i<v.size())nv[i]+=v[i];
if(nv[i]<x)continue;
int g=nv[i]/x;
if(g%2)nv[i+1]+=(((g-1)*x)/2),nv[i]-=(g-1)*x;
else nv[i+1]+=(((g-2)*x)/2),nv[i]-=(g-2)*x;
}//change at dp part
int idk=3*k*x;
vector<vector<int>>dp(2,vector<int>(idk+2,0));
dp[0][0]=1;
for(int i=0;i<k-1;i++){
int cur=(i%2),nx=(i%2)^1;
for(int j=idk;j>=0;j--){
if(j>=nv[i])dp[cur][j]=dp[cur][j-nv[i]];
else dp[cur][j]=0;
if(j-x>=0)dp[nx][(j-x)/2]+=dp[cur][j];
dp[nx][(j/2)]+=dp[cur][j];
dp[cur][j]=0;
}
}
sum=0;
for(int i=0;i<=idk;i++){
int val=dp[(k-1)%2][i],have=nv[k-1]+i;
have/=x;
sum+=(val*(have+1));
}
return sum;
}
else{
int k=v.size();
sum=0;
for(auto i:v)sum+=i;
if(sum>100000)assert(0);
vector<vector<int>>dp(k+63,vector<int>(sum+5,0));
dp[0][0]=1;
for(int i=0;i<=k+61;i++){
if(i<v.size()){
for(int j=sum;j>=v[i];j--)dp[i][j]=dp[i][j-v[i]];//shifting
for(int j=v[i]-1;j>=0;j--)dp[i][j]=0;
}
for(int j=sum;j>=0;j--){
if(j-x>=0)dp[i+1][(j-x)/2]+=dp[i][j];//use x
dp[i+1][(j/2)]+=dp[i][j];//
}
}
int ans=0;
for(int i=0;i<=sum;i++)ans+=dp[k+62][i];
return ans;
}
}/*
int32_t main(){
int t;cin>>t;
while(t--){
int x,k;cin>>x>>k;
vector<int>in(k);
for(int i=0;i<k;i++)cin>>in[i];
cout<<count_tastiness(x,in)<<'\n';
}
}*/
Compilation message
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:47:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(i<v.size())nv[i]+=v[i];
| ~^~~~~~~~~
biscuits.cpp:82:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | if(i<v.size()){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
432 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
29 ms |
11308 KB |
Output is correct |
11 |
Correct |
10 ms |
5976 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
9 ms |
812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
430 ms |
42064 KB |
Output is correct |
2 |
Correct |
5 ms |
1632 KB |
Output is correct |
3 |
Correct |
5 ms |
2000 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Execution timed out |
1014 ms |
43624 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
432 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
29 ms |
11308 KB |
Output is correct |
11 |
Correct |
10 ms |
5976 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
9 ms |
812 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
440 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
430 ms |
42064 KB |
Output is correct |
25 |
Correct |
5 ms |
1632 KB |
Output is correct |
26 |
Correct |
5 ms |
2000 KB |
Output is correct |
27 |
Correct |
0 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
344 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
348 KB |
Output is correct |
31 |
Execution timed out |
1014 ms |
43624 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |