제출 #1054873

#제출 시각아이디문제언어결과실행 시간메모리
1054873Gromp15Packing Biscuits (IOI20_biscuits)C++17
42 / 100
339 ms1628 KiB
#include <bits/stdc++.h> #include "biscuits.h" #define ll long long #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() using namespace std; long long count_tastiness(long long x, std::vector<long long> a) { if (x <= 10001) { map<ll, ll> dp; dp[0] = 1; for (int i = 0; i < sz(a) + 100; i++) { map<ll, ll> dp2; ll cur = i < sz(a) ? a[i] : 0; for (auto [j, val] : dp) { if (j + cur >= x) dp2[(j + cur - x) >> 1] += val; dp2[(j + cur) >> 1] += val; } swap(dp, dp2); } ll ans = 0; for (auto [z, y] : dp) ans += y; return ans; } int ans = 0; auto solve = [&](auto&& s, vector<ll> left, int idx) -> void { if (idx == -1) { ans++; return; } s(s, left, idx - 1); ll cur = x; for (int i = idx; i >= 0; i--) { if (cur > 4e18) break; ll req = min(cur, left[i]); cur -= req, left[i] -= req; if (cur == 0) { s(s, left, min(i, idx - 1)); break; } cur *= 2; } }; solve(solve, a, sz(a) - 1); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...