| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 444057 | fivefourthreeone | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 11;
ll arr[mxN];
ll dp[mxN];
ll x;
ll sumgo(int bit) {
ll ret = 1;
owo(i, 0, bit+1) {
ret += dp[i];
}
return ret;
}
ll go(int bit, ll loss) {
//take this bit
ll ret = 0;
if(arr[bit] - loss >= x) {
//no loss
ret += sumgo(bit-1);
}else {
ll req = (x - arr[bit]) << 1LL;
uwu(i, bit, 0) {
if(arr[i] >= req) {
ret += go(i, req) + sumgo(i-1);
break;
}else {
req = (req - arr[i]) << 1LL;
}
}
}
return ret;
}
ll count_tastiness(int k, vector<int> f) {
x = k;
int n = f.size();
ll res = 0;
memset(arr, 0, sizeof(arr));
memset(dp, 0, sizeof(dp));
owo(i, 0, mxN) {
if(i < n)arr[i] += f[i];
if(arr[i] > x) {
arr[i+1] = (arr[i] - x) / 2LL;
arr[i] -= arr[i+1]*2LL;
}
//cout<<i<<" "<<arr[i]<<"\n";
}
owo(i, 0, mxN) {
dp[i] = go(i, 0);
//cout<<i<<" "<<dp[i]<<" dp...\n";
res += dp[i];
}
return res+1;
}