| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1071610 | Ausp3x | Packing Biscuits (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 人外有人，天外有天
// 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