| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1073657 | 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;
int x;
int K = 60;
vector<lng> T, B;
unordered_map<lng, lng> memo;
lng dp(lng n) {
if (memo.contains(n))
return memo[n];
if (n <= 0)
return 0;
if (n == 1)
return memo[n] = 1;
int i = 63 - __builtin_clzll(n - 1);
return memo[n] = dp(1 << i) + dp(min(B[i] / x + 1, n) - (1 << i));
}
lng count_tastiness(lng given_x, vector<lng> A) {
x = given_x;
A.resize(K);
lng total_tastiness = 0;
T.clear();
B.clear();
T.resize(K);
B.resize(K);
for (int i = 0; i < K; i++) {
T[i] = 1ll << i;
total_tastiness += A[i] * T[i];
B[i] = total_tastiness;
}
if (x > total_tastiness)
return 1;
if (total_tastiness <= 100'000) {
lng ans = 1;
for (int i = 1; i <= total_tastiness / x; i++) {
vector<lng> 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(req_cookies[j] - A[j], 0ll);
ans += req_cookies[0] <= A[0];
}
#ifdef DEBUG
cout << ans << ' ';
#endif
#ifndef DEBUG
return ans;
#endif
}
if (x == 1) {
for (int i = 0; i < K - 1; i++) {
lng q = (A[i] - 1) / 2;
A[i + 1] += q;
A[i] -= 2 * q;
}
// cout << endl;
// for (int a : A)
// cout << a << ' ';
// cout << endl;
int i_o = -1;
lng cur = 0;
vector<lng> A_reduced;
for (int i = 0; i < K; i++) {
if (cur < T[i]) {
i_o = i;
cur = 0;
A_reduced.pb(0);
}
cur += A[i] * T[i];
A_reduced.back() += A[i] * T[i - i_o];
}
lng ans = 1;
for (lng a_r : A_reduced) {
// cout << a_r << ' ';
ans *= a_r + 1;
}
// cout << endl;
#ifdef DEBUG
cout << ans << ' ';
#endif
#ifndef DEBUG
return ans;
#endif
}
return dp(1ll << 60);
}
#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