oj.uz

Submission #673149

# Submission time Handle Problem Language Result Execution time Memory
673149 2022-12-19T20:11:40 Z US3RN4M3 Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 9620 KB 
#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() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9616 KB Output is correct
2 Correct 61 ms 6208 KB Output is correct
3 Correct 25 ms 7048 KB Output is correct
4 Correct 178 ms 7108 KB Output is correct
5 Correct 1 ms 2900 KB Output is correct
6 Correct 2726 ms 9576 KB Output is correct
7 Correct 1183 ms 6160 KB Output is correct
8 Correct 2720 ms 9480 KB Output is correct
9 Correct 3086 ms 9572 KB Output is correct
10 Correct 64 ms 2900 KB Output is correct
11 Correct 123 ms 3028 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9616 KB Output is correct
2 Correct 61 ms 6208 KB Output is correct
3 Correct 25 ms 7048 KB Output is correct
4 Correct 178 ms 7108 KB Output is correct
5 Correct 1 ms 2900 KB Output is correct
6 Correct 2726 ms 9576 KB Output is correct
7 Correct 1183 ms 6160 KB Output is correct
8 Correct 2720 ms 9480 KB Output is correct
9 Correct 3086 ms 9572 KB Output is correct
10 Correct 64 ms 2900 KB Output is correct
11 Correct 123 ms 3028 KB Output is correct
12 Correct 83 ms 9620 KB Output is correct
13 Correct 61 ms 6272 KB Output is correct
14 Correct 25 ms 7100 KB Output is correct
15 Correct 177 ms 7104 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2735 ms 9508 KB Output is correct
18 Correct 1186 ms 6192 KB Output is correct
19 Correct 2724 ms 9588 KB Output is correct
20 Correct 3098 ms 9604 KB Output is correct
21 Correct 65 ms 3028 KB Output is correct
22 Correct 121 ms 3028 KB Output is correct
23 Execution timed out 5078 ms 9588 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7088 KB Output is correct
2 Incorrect 1 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7088 KB Output is correct
2 Incorrect 1 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7088 KB Output is correct
2 Incorrect 1 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9616 KB Output is correct
2 Correct 61 ms 6208 KB Output is correct
3 Correct 25 ms 7048 KB Output is correct
4 Correct 178 ms 7108 KB Output is correct
5 Correct 1 ms 2900 KB Output is correct
6 Correct 2726 ms 9576 KB Output is correct
7 Correct 1183 ms 6160 KB Output is correct
8 Correct 2720 ms 9480 KB Output is correct
9 Correct 3086 ms 9572 KB Output is correct
10 Correct 64 ms 2900 KB Output is correct
11 Correct 123 ms 3028 KB Output is correct
12 Correct 182 ms 7088 KB Output is correct
13 Incorrect 1 ms 2900 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7088 KB Output is correct
2 Incorrect 1 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9616 KB Output is correct
2 Correct 61 ms 6208 KB Output is correct
3 Correct 25 ms 7048 KB Output is correct
4 Correct 178 ms 7108 KB Output is correct
5 Correct 1 ms 2900 KB Output is correct
6 Correct 2726 ms 9576 KB Output is correct
7 Correct 1183 ms 6160 KB Output is correct
8 Correct 2720 ms 9480 KB Output is correct
9 Correct 3086 ms 9572 KB Output is correct
10 Correct 64 ms 2900 KB Output is correct
11 Correct 123 ms 3028 KB Output is correct
12 Correct 83 ms 9620 KB Output is correct
13 Correct 61 ms 6272 KB Output is correct
14 Correct 25 ms 7100 KB Output is correct
15 Correct 177 ms 7104 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2735 ms 9508 KB Output is correct
18 Correct 1186 ms 6192 KB Output is correct
19 Correct 2724 ms 9588 KB Output is correct
20 Correct 3098 ms 9604 KB Output is correct
21 Correct 65 ms 3028 KB Output is correct
22 Correct 121 ms 3028 KB Output is correct
23 Execution timed out 5078 ms 9588 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7088 KB Output is correct
2 Incorrect 1 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 9616 KB Output is correct
2 Correct 61 ms 6208 KB Output is correct
3 Correct 25 ms 7048 KB Output is correct
4 Correct 178 ms 7108 KB Output is correct
5 Correct 1 ms 2900 KB Output is correct
6 Correct 2726 ms 9576 KB Output is correct
7 Correct 1183 ms 6160 KB Output is correct
8 Correct 2720 ms 9480 KB Output is correct
9 Correct 3086 ms 9572 KB Output is correct
10 Correct 64 ms 2900 KB Output is correct
11 Correct 123 ms 3028 KB Output is correct
12 Correct 83 ms 9620 KB Output is correct
13 Correct 61 ms 6272 KB Output is correct
14 Correct 25 ms 7100 KB Output is correct
15 Correct 177 ms 7104 KB Output is correct
16 Correct 2 ms 2900 KB Output is correct
17 Correct 2735 ms 9508 KB Output is correct
18 Correct 1186 ms 6192 KB Output is correct
19 Correct 2724 ms 9588 KB Output is correct
20 Correct 3098 ms 9604 KB Output is correct
21 Correct 65 ms 3028 KB Output is correct
22 Correct 121 ms 3028 KB Output is correct
23 Execution timed out 5078 ms 9588 KB Time limit exceeded
24 Halted 0 ms 0 KB -