(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #409114

#TimeUsernameProblemLanguageResultExecution timeMemory
409114priority_queuePacking Biscuits (IOI20_biscuits)C++14
100 / 100
178 ms1476 KiB
#include <bits/stdc++.h> #define forint(i, N) for (long long i = 0; i < (N); i++) using namespace std; unordered_map<long long, long long> m; long long count(long long x, vector<long long>& a, long long max_y) { if (m[max_y] != 0) { return m[max_y]; } if (max_y == 0) { m[0] = 1; return 1; } if (max_y == 1) { if (a[0] >= x) { m[1] = 2; return 2; // 0 & 1; } else { m[1] = 1; return 1; // 0 only } } long long k = a.size(); vector<long long> sum(61, 0); sum[0] = a[0]; for (long long i = 1; i < k; i++) { sum[i] = sum[i - 1] + a[i] * (1ll << i); } for (long long i = k; i < 61; i++) { sum[i] = sum[i-1]; } long long i = 0; while ((1ll << i) < max_y) { i++; } if (max_y == (1ll << i)) { if (sum[i] / x >= max_y) { m[max_y] = count(x, a, max_y - 1) + 1; return m[max_y]; } else { m[max_y] = count(x, a, max_y - 1); return m[max_y]; } } long long aa = count(x, a, 1ll << (i-1)); if (sum[i-1] / (1ll << (i-1)) < x ) { m[max_y] = aa; return m[max_y]; } else { m[max_y] = aa + count(x, a, min(max_y - (1ll << (i-1)), sum[i-1]/x - (1ll << (i-1)))) - 1; // (1ll << (i-1)) double counted return m[max_y]; } } long long count_tastiness(long long x, vector<long long> a) { m.clear(); return count(x, a, 1e18); }
#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...