#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 55;
const int mx2 = mx*mx*mx;
const ll inf = 1e18;
const ll ninf = -1e18;
ll m, l;
ll cnt_neg[mx];
ll cnt_pos[mx];
ll cnt_zero;
ll dp[mx2*2];
ll cnt_pos_good[mx];
ll cnt_pos_bad[mx];
ll cnt_neg_good[mx];
ll cnt_neg_bad[mx];
ll solve() {
if(l >= mx2 || l < mx2) return -1;
dp[mx2] = cnt_zero;
for(int i = 1; i <= m; i++) {
/* positive good */
if(cnt_pos_good[i]) {
for(int residue = 0; residue < i; residue++) {
map<ll, ll> vals;
vector<ll> history;
ll t = 0;
for(int cur_pos = residue; cur_pos < mx2*2; cur_pos += i) {
ll tmp_val = dp[cur_pos] - t;
if(vals.size())
dp[cur_pos] = max(dp[cur_pos], vals.rbegin()->first + t);
vals[tmp_val]++;
history.push_back(tmp_val);
if(t >= cnt_pos_good[i]) {
ll tmp = history[t - cnt_pos_good[i]];
vals[tmp]--;
if(vals[tmp] == 0) vals.erase(tmp);
}
t++;
}
}
}
/* positive bad */
if(cnt_pos_bad[i]) {
for(int residue = 0; residue < i; residue++) {
map<ll, ll> vals;
vector<ll> history;
ll t = 0;
for(int cur_pos = residue; cur_pos < mx2*2; cur_pos += i) {
ll tmp_val = dp[cur_pos] + t;
if(vals.size())
dp[cur_pos] = max(dp[cur_pos], vals.rbegin()->first - t);
vals[tmp_val]++;
history.push_back(tmp_val);
if(t >= cnt_pos_bad[i]) {
ll tmp = history[t - cnt_pos_bad[i]];
vals[tmp]--;
if(vals[tmp] == 0) vals.erase(tmp);
}
t++;
}
}
}
/* negitive good */
if(cnt_neg_good[i]) {
for(int residue = 0; residue < i; residue++) {
map<ll, ll> vals;
vector<ll> history;
ll t = 0;
for(int cur_neg = mx2*2 - 1 - residue; cur_neg >= 0; cur_neg -= i) {
ll tmp_val = dp[cur_neg] - t;
if(vals.size())
dp[cur_neg] = max(dp[cur_neg], vals.rbegin()->first + t);
vals[tmp_val]++;
history.push_back(tmp_val);
if(t >= cnt_neg_good[i]) {
ll tmp = history[t - cnt_neg_good[i]];
vals[tmp]--;
if(vals[tmp] == 0) vals.erase(tmp);
}
t++;
}
}
}
/* negitive bad */
if(cnt_neg_bad[i]) {
for(int residue = 0; residue < i; residue++) {
map<ll, ll> vals;
vector<ll> history;
ll t = 0;
for(int cur_neg = mx2*2 - 1 - residue; cur_neg >= 0; cur_neg -= i) {
ll tmp_val = dp[cur_neg] + t;
if(vals.size())
dp[cur_neg] = max(dp[cur_neg], vals.rbegin()->first - t);
vals[tmp_val]++;
history.push_back(tmp_val);
if(t >= cnt_neg_bad[i]) {
ll tmp = history[t - cnt_neg_bad[i]];
vals[tmp]--;
if(vals[tmp] == 0) vals.erase(tmp);
}
t++;
}
}
}
}
return dp[mx2 + l];
}
void eq() {
ll total_cnt = cnt_zero;
for(int i = 1; i <= m; i++) {
total_cnt += cnt_neg[i] + cnt_pos[i];
}
cout << total_cnt << endl;
exit(0);
}
void more_pos() {
for(int i = 1; i <= m; i++) {
cnt_neg_good[i] = cnt_neg[i];
cnt_pos_good[i] = cnt_pos[i];
}
ll res = solve();
if(res < 0) cout << "impossible" << endl;
else cout << res << endl;
}
void more_neg() {
for(int i = 1; i <= m; i++) {
swap(cnt_pos[i], cnt_neg[i]);
}
l *= -1;
more_pos();
}
main() {
for(int i = 0; i < mx2*2; i++) dp[i] = ninf;
cin >> m >> l;
ll sum_pos = 0;
ll sum_neg = 0;
for(int i = m; i >= 1; i--) {
cin >> cnt_neg[i];
sum_neg += cnt_neg[i] * i;
}
cin >> cnt_zero;
for(int i = 1; i <= m; i++) {
cin >> cnt_pos[i];
sum_pos += cnt_pos[i] * i;
}
if(sum_pos < l) {
cout << "impossible" << endl;
return 0;
}
if(l > sum_pos) {
cout << "impossible" << endl;
return 0;
}
if(sum_pos + sum_neg == l) eq();
if(sum_pos - sum_neg > l) more_pos();
if(sum_pos - sum_neg < l) more_neg();
}
Compilation message
vault.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
132 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
