#include "biscuits.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()
constexpr ll inf = (1ll<<60);
ll subtask_1_2_3(ll x, vi a){
ll k = a.size();
while(k <= 60){
a.pb(0);
k++;
}
//assert(x <= 10000);
vi remain(1,0), val(1,1);
rep(i,0,k){
vector<pii> data;
rep(j,0,remain.size()){
data.pb(mp((remain[j]+a[i])/2, val[j]));
if(remain[j]+a[i] >= x){
data.pb(mp((remain[j]+a[i]-x)/2, val[j]));
}
}
sort(all(data));
remain.clear();
val.clear();
remain.pb(data[0].first);
val.pb(0);
for(auto el: data){
if(el.first == remain.back()) val[val.size()-1] += el.second;
else{
remain.pb(el.first);
val.pb(el.second);
}
}
}
ll ans = 0;
for(auto el: val) ans += el;
return ans;
}
long long count_tastiness(long long x, std::vector<long long> a) {
//if(x <= 10000) return subtask_1_2_3(x,a);
ll k = a.size();
while(k <= 60){
a.pb(0);
k++;
}
vi sum(k);
rep(i,0,k){
if(i) sum[i] = sum[i-1];
sum[i] += (1ll<<i)*a[i];
}
vi dp(k);
vi require(k);
rep(i,0,k){
if(sum[i]/(1ll<<i) < x){
require[i] = -1;
continue;
}
else{
require[i] = (sum[i]-(1ll<<i)*x)/x;
}
}
per(i,k-1,0){
if(require[i] == -1) continue;
dp[i]++;
if(require[i] >= (1ll<<i)){
rep(j,0,i){
if(require[j] != -1) dp[j] += dp[i];
}
continue;
}
ll cnt = 0;
per(j,i-1,0){
if(require[j] != -1){
dp[j] += cnt*dp[i];
}
if(require[i] & (1ll<<j)){
if(require[j] == -1){
cnt++;
rep(k,0,j){
if(require[k] != -1){
dp[k] += cnt*dp[i];
}
}
break;
}
require[i] -= (1ll<<j);
if(require[i] >= require[j]){
cnt++;
REP(k,0,j){
if(require[k] != -1){
dp[k] += cnt*dp[i];
}
}
break;
}
cnt++;
}
}
}
ll ans = 1;
rep(i,0,k){
if(require[i] == -1) continue;
ans += dp[i];
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
