Submission #634766

#TimeUsernameProblemLanguageResultExecution timeMemory
634766null_aweUplifting Excursion (BOI22_vault)C++14
0 / 100
0 ms212 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define ll long long int main() { int n; cin >> n; n = 2 * n + 1; ll l; cin >> l; vector<ll> arr(n); for (int i = 0; i < n; ++i) cin >> arr[i]; if (l < 0) reverse(arr.begin(), arr.end()), l = -l; for (int i = 0; i < n / 2; ++i) arr[n - 1 - i] += arr[i], l += (n / 2 - i) * arr[i], arr[i] = 0; ll sum = 0; vector<ll> count(n / 2 + 1); count[0] = arr[n / 2]; for (int rep = 0; rep < n / 2; ++rep) { for (int i = 1; i <= n / 2; ++i) { if (sum == l) break; if (arr[i + n / 2] * i + sum <= l) sum += arr[i + n / 2] * i, swap(count[i], arr[i + n / 2]); else { int take = (l - sum) / i; sum += i * take, count[i] += take, arr[i + n / 2] -= take; //cout << sum << '\n'; int sum2 = 0; vector<ll> copy = count, copy2 = arr; for (int j = i; j > 0; --j) { while (count[j]) { if (sum2 >= i + sum - l) break; --count[j], ++arr[j + n / 2], sum2 += j; } if (count[j]) break; } if (sum + i - sum2 > l) { count = copy, arr = copy2; continue; } sum += i - sum2; ++count[i], --arr[i + n / 2]; } //cout << sum << '\n'; } if (sum != l) cout << "impossible\n"; else { ll ans = 0; for (ll num : count) ans += num; cout << ans << '\n'; } } return 0; }
#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...
#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...