| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1019612 | TheWilp | 비스킷 담기 (IOI20_biscuits) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "biscuits.h"
#include <algorithm>
#include <queue>
#include <iostream>
using ll = long long;
std::vector<ll> ori_dp;
std::vector<ll> sum_ori_dp;
long long func1(long long x,std::vector<long long> a) {
if(a.size() == 0) return 1;
if(a.size() == 1) return a.back() >= x ? 2 : 1;
ll ans = sum_ori_dp[a.size() - 2];
std::vector<ll> s(a.begin(),a.begin() + a.size() - 1);
ll require = x - a.back();
while(require > 0 && s.size()) {
require *= 2;
if(require >= 2ll * 1e18) return;
if(require >= s.back()) {
require -= s.back();
s.pop_back();
}
else {
s.back() -= require;
require = 0;
break;
}
}
while(s.back() == 0 && s.size()) s.pop_back();
if(require <= 0) ans += func1(x,s);
return ans;
}
long long count_tastiness(long long x, std::vector<long long> a) {
std::vector<ll> new_a;
ll c = 0;
for(int q = 0;q < a.size();q++) {
c /= 2;
c += a[q];
if(c >= x) {
new_a.push_back(x);
c -= x;
}
else {
new_a.push_back(c);
c = 0;
}
}
while(c > 0) {
c /= 2;
if(c >= x) {
new_a.push_back(x);
c -= x;
}
else {
new_a.push_back(c);
c = 0;
}
}
a = new_a;
ori_dp.clear();
sum_ori_dp.clear();
ori_dp.push_back(a[0] >= x ? 2 : 1);
sum_ori_dp.push_back(a[0] >= x ? 2 : 1);
for(int q = 1;q < a.size();q++) {
ll local_ans = 0;
std::vector<ll> s(a.begin(),a.begin() + q);
ll require = x - a[q];
while(require > 0 && s.size()) {
require *= 2;
if(require > 2ll * 1e18) break;
if(s.back() <= require) {
require -= s.back();
s.pop_back();
}
else {
s.back() -= require;
require = 0;
break;
}
}
while(s.back() == 0 && s.size()) s.pop_back();
if(require <= 0)
local_ans += func1(x,s);
//std::cout << "local ans" << local_ans << std::endl;
ori_dp.push_back(local_ans);
sum_ori_dp.push_back(sum_ori_dp.back() + ori_dp.back());
}
// for(int q = 0;q < ori_dp.size();q++) {
// std::cout << ori_dp[q] << " ";
// }
// std::cout << std::endl;
return sum_ori_dp.back();
}
// #include <cassert>
// #include <cstdio>
// using namespace std;
// 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%lld", &k[t], &x[t]) == 2);
// a[t] = vector<long long>(k[t]);
// for (int i = 0; i < k[t]; i++) {
// assert(scanf("%lld", &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("%lld\n", results[t]);
// }
// fclose(stdout);
// return 0;
// }