#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
vector<int> calc(vector<int> x) {
int S = accumulate(x.begin(), x.end(), 0);
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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
78 ms |
576 KB |
Output is correct |
6 |
Correct |
79 ms |
584 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
77 ms |
440 KB |
Output is correct |
9 |
Correct |
314 ms |
804 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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
78 ms |
576 KB |
Output is correct |
6 |
Correct |
79 ms |
584 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
77 ms |
440 KB |
Output is correct |
9 |
Correct |
314 ms |
804 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 |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
75 ms |
568 KB |
Output is correct |
17 |
Correct |
89 ms |
580 KB |
Output is correct |
18 |
Correct |
14 ms |
340 KB |
Output is correct |
19 |
Correct |
75 ms |
444 KB |
Output is correct |
20 |
Correct |
288 ms |
696 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
2369 ms |
2356 KB |
Output is correct |
24 |
Correct |
2507 ms |
2288 KB |
Output is correct |
25 |
Correct |
377 ms |
1136 KB |
Output is correct |
26 |
Execution timed out |
5067 ms |
4284 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
517 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 |
517 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 |
517 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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
78 ms |
576 KB |
Output is correct |
6 |
Correct |
79 ms |
584 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
77 ms |
440 KB |
Output is correct |
9 |
Correct |
314 ms |
804 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 |
517 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 |
517 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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
78 ms |
576 KB |
Output is correct |
6 |
Correct |
79 ms |
584 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
77 ms |
440 KB |
Output is correct |
9 |
Correct |
314 ms |
804 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 |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
75 ms |
568 KB |
Output is correct |
17 |
Correct |
89 ms |
580 KB |
Output is correct |
18 |
Correct |
14 ms |
340 KB |
Output is correct |
19 |
Correct |
75 ms |
444 KB |
Output is correct |
20 |
Correct |
288 ms |
696 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
2369 ms |
2356 KB |
Output is correct |
24 |
Correct |
2507 ms |
2288 KB |
Output is correct |
25 |
Correct |
377 ms |
1136 KB |
Output is correct |
26 |
Execution timed out |
5067 ms |
4284 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
517 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 |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
78 ms |
576 KB |
Output is correct |
6 |
Correct |
79 ms |
584 KB |
Output is correct |
7 |
Correct |
15 ms |
340 KB |
Output is correct |
8 |
Correct |
77 ms |
440 KB |
Output is correct |
9 |
Correct |
314 ms |
804 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 |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
75 ms |
568 KB |
Output is correct |
17 |
Correct |
89 ms |
580 KB |
Output is correct |
18 |
Correct |
14 ms |
340 KB |
Output is correct |
19 |
Correct |
75 ms |
444 KB |
Output is correct |
20 |
Correct |
288 ms |
696 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
2369 ms |
2356 KB |
Output is correct |
24 |
Correct |
2507 ms |
2288 KB |
Output is correct |
25 |
Correct |
377 ms |
1136 KB |
Output is correct |
26 |
Execution timed out |
5067 ms |
4284 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |