| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1071610 | Ausp3x | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 人外有人，天外有天
// author: Ausp3x
#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #include "biscuits.h"
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define pb push_back
#define DEBUG
typedef long long lng;
typedef __int128 lli;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;
string getPrintableLli(lli x) {
string x_str;
while (x > 0) {
x_str += '0' + x % 10;
x /= 10;
}
reverse(x_str.begin(), x_str.end());
return x_str;
}
lng count_tastiness(lng x, vector<lng> A) {
int K = 60;
A.resize(K);
lli total_tastiness = 0;
vector<lng> T(K);
for (int i = 0; i < K; i++) {
T[i] = 1ll << i;
total_tastiness += lli(A[i]) * T[i];
}
if (x > total_tastiness)
return 1;
if (total_tastiness <= 100'000) {
lng ans = 1;
for (int i = 1; i <= total_tastiness / x; i++) {
vector<lli> req_cookies(K);
for (int j = 0; j < K; j++)
if (i & T[j])
req_cookies[j] = x;
for (int j = K - 1; j > 0; j--)
req_cookies[j - 1] += 2 * max<lli>(req_cookies[j] - A[j], 0);
ans += req_cookies[0] <= A[0];
}
return ans;
}
return -1;
}
#ifdef DEBUG
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
cin >> t;
while (t--) {
int K;
lng x;
cin >> K >> x;
vector<lng> A(K);
for (lng &a : A)
cin >> a;
cout << count_tastiness(x, A) << endl;
}
return 0;
}
#endif