#include "bits/stdc++.h"
using namespace std;
using ll = long long;
vector<int> calc(vector<int> x) {
int S = (int)x.size() * 100;
vector<int> dp(S + 1, INT_MIN);
dp[0] = 0;
for(int i = 0; i < (int)x.size(); ++i) {
for(int j = S; j >= 0; --j) {
if(j - x[i] >= 0) if(dp[j - x[i]] != INT_MIN) dp[j] = max(dp[j], dp[j - x[i]] + 1);
}
}
return dp;
}
int main() {
ll l, m; cin >> m >> l;
vector<int> a(2 * m + 1);
for(int i = 0; i < 2 * m + 1; ++i) cin >> a[i];
int ans = INT_MIN;
vector<int> neg;
int val = m;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < a[i]; ++j) neg.push_back(val);
--val;
}
vector<int> pos;
val = 1;
for(int i = m + 1; i < 2 * m + 1; ++i) {
for(int j = 0; j < a[i]; ++j) pos.push_back(val);
++val;
}
vector<int> pp = calc(pos);
vector<int> ng = calc(neg);
if(l < 0) {
swap(pp, ng);
l = -l;
}
for(ll sum = l; sum < (int)pp.size(); ++sum) {
if(sum - l >= (int)ng.size() || pp[sum] == INT_MIN || ng[sum - l] == INT_MIN) continue;
ans = max(ans, pp[sum] + ng[sum - l] + a[m]);
}
if(ans == INT_MIN) cout << "impossible\n";
else cout << ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
236 ms |
1292 KB |
Output is correct |
6 |
Correct |
250 ms |
1352 KB |
Output is correct |
7 |
Correct |
70 ms |
716 KB |
Output is correct |
8 |
Correct |
267 ms |
1192 KB |
Output is correct |
9 |
Correct |
908 ms |
2152 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
236 ms |
1292 KB |
Output is correct |
6 |
Correct |
250 ms |
1352 KB |
Output is correct |
7 |
Correct |
70 ms |
716 KB |
Output is correct |
8 |
Correct |
267 ms |
1192 KB |
Output is correct |
9 |
Correct |
908 ms |
2152 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
301 ms |
1292 KB |
Output is correct |
17 |
Correct |
297 ms |
1360 KB |
Output is correct |
18 |
Correct |
65 ms |
720 KB |
Output is correct |
19 |
Correct |
249 ms |
1308 KB |
Output is correct |
20 |
Correct |
952 ms |
2188 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
4069 ms |
4336 KB |
Output is correct |
24 |
Correct |
3940 ms |
4300 KB |
Output is correct |
25 |
Correct |
538 ms |
1832 KB |
Output is correct |
26 |
Execution timed out |
5050 ms |
4180 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
236 ms |
1292 KB |
Output is correct |
6 |
Correct |
250 ms |
1352 KB |
Output is correct |
7 |
Correct |
70 ms |
716 KB |
Output is correct |
8 |
Correct |
267 ms |
1192 KB |
Output is correct |
9 |
Correct |
908 ms |
2152 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
236 ms |
1292 KB |
Output is correct |
6 |
Correct |
250 ms |
1352 KB |
Output is correct |
7 |
Correct |
70 ms |
716 KB |
Output is correct |
8 |
Correct |
267 ms |
1192 KB |
Output is correct |
9 |
Correct |
908 ms |
2152 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
301 ms |
1292 KB |
Output is correct |
17 |
Correct |
297 ms |
1360 KB |
Output is correct |
18 |
Correct |
65 ms |
720 KB |
Output is correct |
19 |
Correct |
249 ms |
1308 KB |
Output is correct |
20 |
Correct |
952 ms |
2188 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
4069 ms |
4336 KB |
Output is correct |
24 |
Correct |
3940 ms |
4300 KB |
Output is correct |
25 |
Correct |
538 ms |
1832 KB |
Output is correct |
26 |
Execution timed out |
5050 ms |
4180 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
554 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
236 ms |
1292 KB |
Output is correct |
6 |
Correct |
250 ms |
1352 KB |
Output is correct |
7 |
Correct |
70 ms |
716 KB |
Output is correct |
8 |
Correct |
267 ms |
1192 KB |
Output is correct |
9 |
Correct |
908 ms |
2152 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
301 ms |
1292 KB |
Output is correct |
17 |
Correct |
297 ms |
1360 KB |
Output is correct |
18 |
Correct |
65 ms |
720 KB |
Output is correct |
19 |
Correct |
249 ms |
1308 KB |
Output is correct |
20 |
Correct |
952 ms |
2188 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
4069 ms |
4336 KB |
Output is correct |
24 |
Correct |
3940 ms |
4300 KB |
Output is correct |
25 |
Correct |
538 ms |
1832 KB |
Output is correct |
26 |
Execution timed out |
5050 ms |
4180 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |