(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.

제출 #303380

#제출 시각아이디문제언어결과실행 시간메모리
303380rama_pang비스킷 담기 (IOI20_biscuits)C++14
100 / 100
17 ms896 KiB
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; long long count_tastiness(long long x, vector<long long> a) { int k = (int) a.size(); auto b = a; for (int i = 1; i < k; i++) { b[i] += b[i - 1] / 2; } while (b.back() > 0) { k += 1; a.emplace_back(0); b.emplace_back(b.back() / 2); } vector<long long> dp_on(k); // dp_on[i] = first i bits, i-th bit is on vector<long long> dp_off(k); // dp_off[i] = first i bits, i-th bit is off for (int i = 0; i < k; i++) { dp_off[i] = (i > 0 ? (dp_on[i - 1] + dp_off[i - 1]) : 1); if (b[i] < x) { dp_on[i] = 0; } else { dp_on[i] = 1; long long need = max(0ll, x - a[i]); for (int j = i - 1; j >= 0; j--) { need = need * 2; if (b[j] >= need + x) { dp_on[i] += dp_off[j]; // turn the j-th bit off need = max(0ll, need + x - a[j]); // turn the j-th bit on } else { need = max(0ll, need - a[j]); // the j-th bit can only be off } } } } return dp_on[k - 1] + dp_off[k - 1]; }
#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...