oj.uz

Submission #673142

# Submission time Handle Problem Language Result Execution time Memory
673142 2022-12-19T19:57:14 Z US3RN4M3 Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 3020 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(int target) {
	dp[target + mx2] = 0;
	for(int i = 1; i <= m; i++) {
		/* positive good */
		if(cnt_pos_good[i]) {
			map<ll, int> vals;
			vector<ll> history;
			int t = 0;
			for(int residue = 0; residue < i; residue++) {
				for(int cur_pos = residue; cur_pos < mx2*2; cur_pos += i) {
					ll tmp_val = dp[cur_pos] + 1;
					if(vals.size())
						dp[cur_pos] = max(dp[cur_pos], vals.rbegin()->first);
					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]) {
			map<ll, int> vals;
			vector<ll> history;
			int t = 0;
			for(int residue = 0; residue < i; residue++) {
				for(int cur_pos = residue; cur_pos < mx2*2; cur_pos += i) {
					ll tmp_val = dp[cur_pos] - 1;
					if(vals.size())
						dp[cur_pos] = max(dp[cur_pos], vals.rbegin()->first);
					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]) {
			map<ll, int> vals;
			vector<ll> history;
			int t = 0;
			for(int residue = 0; residue < i; residue++) {
				for(int cur_neg = mx2*2 - 1 - residue; cur_neg >= 0; cur_neg -= i) {
					ll tmp_val = dp[cur_neg] + 1;
					if(vals.size())
						dp[cur_neg] = max(dp[cur_neg], vals.rbegin()->first);
					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]) {
			map<ll, int> vals;
			vector<ll> history;
			int t = 0;
			for(int residue = 0; residue < i; residue++) {
				for(int cur_neg = mx2*2 - 1 - residue; cur_neg >= 0; cur_neg -= i) {
					ll tmp_val = dp[cur_neg] - 1;
					if(vals.size())
						dp[cur_neg] = max(dp[cur_neg], vals.rbegin()->first);
					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];
}
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_pos2() {
	ll sum_neg = l;
	for(int i = 1; i <= m; i++) {
		sum_neg += cnt_neg[i] * i;
	}
	/* binary search: */
	ll cnt_pos_used = 0;
	for(ll delta = (1ll<<60); delta >= 1; delta >>= 1) {
		ll test_value = cnt_pos_used + delta;
		ll cur_sum = 0;
		ll remaining = test_value;
		for(int i = 1; i <= m; i++) {
			if(cnt_pos[i] >= remaining) {
				cur_sum += remaining * i;
				remaining = 0;
				break;
			} else {
				cur_sum += cnt_pos[i] * i;
				remaining -= cnt_pos[i];
			}
		}
		if(remaining > 0) continue;
		if(cur_sum < sum_neg) cnt_pos_used = test_value;
	}
	cnt_pos_used++;
	ll target = -sum_neg;
	ll remaining = cnt_pos_used;
	ll ans = cnt_pos_used + cnt_zero;
	for(int i = 1; i <= m; i++) {
		if(remaining <= cnt_pos[i]) {
			cnt_pos_good[i] = cnt_pos[i] - remaining;
			cnt_neg_bad[i] = remaining;
			target += remaining * i;
			remaining = 0;
		} else {
			cnt_neg_bad[i] = cnt_pos[i];
			target += cnt_pos[i] * i;
			remaining -= cnt_pos[i];
		}
		cnt_pos_bad[i] = cnt_neg[i];
		ans += cnt_neg[i];
	}
	ans += solve(target);
	if(ans < 0) cout << "impossible" << endl;
	else cout << ans << endl;
}
void more_pos() {
	dp[mx2] = cnt_zero;
	for(int i = 1; i <= m; i++) {
		for(int _ = 0; _ < cnt_pos[i]; _++) {
			for(int j = mx2*2 - 1 - i; j >= 0; j--) {
				dp[j + i] = max(dp[j + i], dp[j] + 1);
			}
		}
		for(int _ = 0; _ < cnt_neg[i]; _++) {
			for(int j = i; j < mx2*2; j++) {
				dp[j - i] = max(dp[j - i], dp[j] + 1);
			}
		}
	}
	if(l < -mx2 || l >= mx2 || dp[mx2 + l] < 0) cout << "impossible" << endl;
	else cout << dp[mx2 + l] << 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(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:185:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  185 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 679 ms 2900 KB Output is correct
6 Correct 724 ms 2900 KB Output is correct
7 Correct 289 ms 2900 KB Output is correct
8 Correct 691 ms 2900 KB Output is correct
9 Correct 1285 ms 2900 KB Output is correct
10 Correct 36 ms 3020 KB Output is correct
11 Correct 25 ms 2900 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 679 ms 2900 KB Output is correct
6 Correct 724 ms 2900 KB Output is correct
7 Correct 289 ms 2900 KB Output is correct
8 Correct 691 ms 2900 KB Output is correct
9 Correct 1285 ms 2900 KB Output is correct
10 Correct 36 ms 3020 KB Output is correct
11 Correct 25 ms 2900 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 3 ms 2904 KB Output is correct
15 Correct 16 ms 2900 KB Output is correct
16 Correct 670 ms 2900 KB Output is correct
17 Correct 717 ms 2900 KB Output is correct
18 Correct 285 ms 2900 KB Output is correct
19 Correct 688 ms 2900 KB Output is correct
20 Correct 1281 ms 2900 KB Output is correct
21 Correct 29 ms 2900 KB Output is correct
22 Correct 25 ms 2900 KB Output is correct
23 Incorrect 1860 ms 2900 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Execution timed out 5099 ms 2900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Execution timed out 5099 ms 2900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Execution timed out 5099 ms 2900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 679 ms 2900 KB Output is correct
6 Correct 724 ms 2900 KB Output is correct
7 Correct 289 ms 2900 KB Output is correct
8 Correct 691 ms 2900 KB Output is correct
9 Correct 1285 ms 2900 KB Output is correct
10 Correct 36 ms 3020 KB Output is correct
11 Correct 25 ms 2900 KB Output is correct
12 Correct 16 ms 2900 KB Output is correct
13 Execution timed out 5099 ms 2900 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Execution timed out 5099 ms 2900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 679 ms 2900 KB Output is correct
6 Correct 724 ms 2900 KB Output is correct
7 Correct 289 ms 2900 KB Output is correct
8 Correct 691 ms 2900 KB Output is correct
9 Correct 1285 ms 2900 KB Output is correct
10 Correct 36 ms 3020 KB Output is correct
11 Correct 25 ms 2900 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 3 ms 2904 KB Output is correct
15 Correct 16 ms 2900 KB Output is correct
16 Correct 670 ms 2900 KB Output is correct
17 Correct 717 ms 2900 KB Output is correct
18 Correct 285 ms 2900 KB Output is correct
19 Correct 688 ms 2900 KB Output is correct
20 Correct 1281 ms 2900 KB Output is correct
21 Correct 29 ms 2900 KB Output is correct
22 Correct 25 ms 2900 KB Output is correct
23 Incorrect 1860 ms 2900 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2900 KB Output is correct
2 Execution timed out 5099 ms 2900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 18 ms 2884 KB Output is correct
5 Correct 679 ms 2900 KB Output is correct
6 Correct 724 ms 2900 KB Output is correct
7 Correct 289 ms 2900 KB Output is correct
8 Correct 691 ms 2900 KB Output is correct
9 Correct 1285 ms 2900 KB Output is correct
10 Correct 36 ms 3020 KB Output is correct
11 Correct 25 ms 2900 KB Output is correct
12 Correct 5 ms 2900 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 3 ms 2904 KB Output is correct
15 Correct 16 ms 2900 KB Output is correct
16 Correct 670 ms 2900 KB Output is correct
17 Correct 717 ms 2900 KB Output is correct
18 Correct 285 ms 2900 KB Output is correct
19 Correct 688 ms 2900 KB Output is correct
20 Correct 1281 ms 2900 KB Output is correct
21 Correct 29 ms 2900 KB Output is correct
22 Correct 25 ms 2900 KB Output is correct
23 Incorrect 1860 ms 2900 KB Output isn't correct
24 Halted 0 ms 0 KB -