| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 563889 | topovik | 비스킷 담기 (IOI20_biscuits) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "biscuits.h"
#include <cassert>
#include <cstdio>
#define pb push_back
using namespace std;
typedef long long ll;
#ifdef _WIN32
# define I64 "%I64d"
#else
# define I64 "%lld"
#endif
long long count_tastiness(long long, std::vector<long long>);
int main () {
int q;
assert(scanf("%d", &q) == 1);
vector<int> k(q);
vector<long long> x(q);
vector<vector<long long>> a(q);
vector<long long> results(q);
for (int t = 0; t < q; t++) {
assert(scanf("%d" I64, &k[t], &x[t]) == 2);
a[t] = vector<long long>(k[t]);
for (int i = 0; i < k[t]; i++)
assert(scanf(I64, &a[t][i]) == 1);
}
fclose(stdin);
for (int t = 0; t < q; t++)
results[t] = count_tastiness(x[t], a[t]);
for (int t = 0; t < q; t++)
printf(I64 "\n", results[t]);
fclose(stdout);
return 0;
}
const int M = 61;
long long count_tastiness(long long x, std::vector<long long> a) {
while (a.size() < M) a.pb(0);
vector <ll> b = a;
for (int i = 1; i < M; i++) b[i] += b[i - 1] / 2ll;
ll dp[M + 1];
dp[0] = 1;
for (int i = 0; i < M; i++)
{
dp[i + 1] = dp[i];
ll need = max(0ll, (x - a[i]) * 2ll);
for (int j = i - 1; j >= 0; j--)
{
if (b[j] >= x + need)
{
dp[i + 1] += dp[j];
need = max((x + need - a[j]) * 2ll, 0ll);
}
else need = max((need - a[j]) * 2ll, 0ll);
}
if (need == 0) dp[i + 1]++;
}
return dp[M];
}