Submission #834168

#TimeUsernameProblemLanguageResultExecution timeMemory
834168JohannPacking Biscuits (IOI20_biscuits)C++14
12 / 100
8 ms1108 KiB
#include "biscuits.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef vector<ll> vi; typedef vector<vi> vvi; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() ll X; long long count_tastiness(long long _X, std::vector<long long> a) { vi b; X = _X; for (int i = 0; i < sz(a); ++i) { if (a[i] >= X && i + 1 >= sz(a)) a.push_back(0); ll tmp = a[i] / X; if (tmp & 1) b.push_back(1); else b.push_back(min(2LL, tmp)); if (i + 1 < sz(a)) a[i + 1] += (a[i] - b.back() * X) / 2; } if (b.back() != 0) b.push_back(0); vvi dp(sz(b), vi(3, 0)); if (b.back() == 0) dp.back()[2] = 1; else if (b.back() == 1) dp.back()[0] = dp.back()[1] = 1; else dp.back()[0] = dp.back()[1] = dp.back()[2] = 1; for (int i = sz(b) - 2; i >= 0; --i) { ll total = dp[i + 1][0] + dp[i + 1][1] + dp[i + 1][2]; if (b[i] == 0) { dp[i][2] = total; } else if (b[i] == 1) { dp[i][0] = dp[i][1] = total; } else { dp[i][0] = dp[i][1] = total; int j = i + 1; while (j < sz(b)) { dp[i][2] += dp[j][2]; if (b[j] == 1) ++j; else break; } } } return dp[0][0] + dp[0][1] + dp[0][2]; }
#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...