| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 444057 | fivefourthreeone | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}