| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1181393 | browntoad | 비스킷 담기 (IOI20_biscuits) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "grader.cpp"
#include "biscuits.h"
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
const ll maxn = 1e5+5;
const int bloc = 101;
long long count_tastiness(long long x, std::vector<long long> a) {
ll mxval = 0;
REP(i, SZ(a)){
mxval += (1ll<<i) * a[i];
}
mxval /= x;
//ll cnt = 1;
ll cur = 0, ptr = 1;
vector<ll> dp(60), pfa(60);
for (int j = 0; j < 60;j++){
if (j < SZ(a)) cur += a[j] * (1ll<<j);
pfa[j] = min(cur/x, (1ll<<j+1)-1);
if ((1ll<<j) > mxval) {
if (j > 0) dp[j] = dp[j-1];
else dp[j] = 1;
continue;
}
/*ll optr = ptr, v;
REP(i, optr){
v = okie[i];
if (v + (1ll<<j) > mxval) break;
if ((v + (1ll<<j))*x > cur) break;
okie[ptr++] = (v|(1ll<<j));
}
*/
ll tmp = cur, cpos = j;
while(cpos >= 0){
tmp = min(pfa[cpos], tmp);
if (!(tmp&(1ll<<cpos))) {
cpos--;
continue;
}
if (cpos > 0) dp[j] += dp[cpos-1];
else dp[j]++;
//dp[j]++; // end itself as 1
tmp -= (1ll<<cpos);
cpos--;
}
dp[j]++;
//cout<<dp[j]<<endl;
}
return dp[59];
//return 0;
}
// answer(j) = answer(j-1) + (if exist bit, after modification)-> answer(j-1)
/*
1
3 3
5 2 1
1
3 2
2 1 2
1
1 1
2
*/