#include <bits/stdc++.h>
using namespace std;
void update(int minVal, int S, vector<int> &dp, int l, long long a, int w) {
if(l > 0){
for(int i = 0; i < l; i++){
deque<pair<int, int> > val;
for(int j = i; j >= 0 && j <= 2 * S; j += l){
while(!val.empty() && (j - val.front().first)/l > a){
val.pop_front();
}
while(!val.empty() && dp[j] >= val.back().second + (j - val.back().first)/l * w){
val.pop_back();
}
if(dp[j] > minVal){
val.emplace_back(make_pair(j, dp[j]));
}
if(!val.empty()){
dp[j] = max(dp[j], val.front().second + (j - val.front().first)/l * w);
}
}
}
}
else{
for(int i = 2 * S; i > 2 * S + l; i -= 1){
deque<pair<int, int> > val;
for(int j = i; j >= 0 && j <= 2 * S; j += l){
while(!val.empty() && (j - val.front().first)/l > a){
val.pop_front();
}
while(!val.empty() && dp[j] >= val.back().second + (j - val.back().first)/l * w){
val.pop_back();
}
if(dp[j] > minVal){
val.emplace_back(make_pair(j, dp[j]));
}
if(!val.empty()){
dp[j] = max(dp[j], val.front().second + (j - val.front().first)/l * w);
}
}
}
}
}
int main() {
int m;
cin >> m;
long long l;
cin >> l;
long long x = 0;
long long sum = 0;
vector<long long> a(2 * m + 1);
for(int i = -m; i <= m; i++){
cin >> a[i + m];
sum += a[i + m] * i;
}
int S = m * m;
int minVal = -2 * m - 1;
vector<int> dp(2 * S + 1);
for(int i = 0; i <= 2 * S; i++){
dp[i] = minVal;
}
dp[S] = 0;
if(sum < l){
for (int i = -m; -m <= i && i <= m; i--){
long long val;
if(l == 0){
val = min(a[i + m], max(0ll, l / i));
}
a[i + m] -= val;
x += val;
l -= val * i;
if (l == 0){
continue;
}
update(minVal, S, dp, i, a[l + m], 1);
update(minVal, S, dp, -i, val, -1);
}
if (-S > l || l > S || dp[l + S] == minVal){
cout << "impossible\n";
}
else{
cout << dp[l + S] + x << "\n";
}
}
else{
for (int i = -m; -m <= i && i <= m; i--){
long long val;
if(l == 0 || (l > 0)){
val = min(a[i + m], max(0ll, l / i));
}
a[i + m] -= val;
x += val;
l -= val * i;
if (l == 0){
continue;
}
update(minVal, S, dp, i, a[l + m], 1);
update(minVal, S, dp, -i, val, -1);
}
if (-S > l || l > S || dp[l + S] == minVal){
cout << "impossible\n";
}
else{
cout << dp[l + S] + x << "\n";
}
}
}
Compilation message
vault.cpp: In function 'int main()':
vault.cpp:91:22: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
91 | a[i + m] -= val;
vault.cpp:71:22: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | l -= val * i;
| ~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
