#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 305;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, L;
int a[N];
int dp[N][2 * N * N];// maximum in the end of i, (maximum possible +- = j)
void process(){
cin >> n >> L;
for(int i = 0; i <= 2 * n; i++) cin >> a[i];
for(int i = 0; i <= n; i++){
for(int j = -(n * n); j <= (n * n); j++) dp[i][j + (n * n)] = -oo;
}
//int answer = -oo;
dp[0][n * n] = a[n];
if(L >= 0 && a[n + 1] >= L){
cout << L;
return;
}
if(L < 0 && a[n - 1] >= -L){
cout << -L;
return;
}
int answer = -oo;
int total = 0;
for(int i = 1; i <= n; i++){
total += (a[n + i] - a[n - i]) * i;
for(int j = -(n * n); j <= (n * n); j++){
//cout << dp[i][j] << "\n;
for(int k = 0; k <= min(a[n - i], n * n); k++){// delete the negatives
int lst = (j - k * i);
if(lst < -(n * n)) break;
dp[i][j + n * n] = max(dp[i][j + n * n], dp[i - 1][lst + n * n] + (a[n - i] + a[n + i] - k));
}
for(int k = 0; k <= min(a[n + i], n * n); k++){
int lst = (j + k * i);
if(lst > (n * n)) break;
dp[i][j + n * n] = max(dp[i][j + n * n], dp[i - 1][lst + n * n] + (a[n - i] + a[n + i] - k));
}
int diff = (L - total - j);
//cout << i << " " << j << " " << total << " " << dp[i][j + n * n] << "\n";
if(!(diff % (i + 1))){
diff /= (i + 1);
if(diff >= 0 && diff <= (a[n + i + 1])) answer = max(answer, dp[i][j + n * n] + diff);
if(i < n && diff < 0 && -diff <= (a[n - i - 1])) answer = max(answer, dp[i][j + n * n] + (-diff));
}
}
}
if(answer >= 0) cout << answer;
else cout << "impossible";
//cout << (answer >= 0 ? answer : "impossible") << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
process();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
