oj.uz

Submission #673136

# Submission time Handle Problem Language Result Execution time Memory
673136 2022-12-19T19:50:58 Z US3RN4M3 Uplifting Excursion (BOI22_vault) C++17
0 / 100
 5000 ms 47640 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 55;
const int mx2 = mx*mx*1000;
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(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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47640 KB Output is correct
2 Correct 61 ms 47636 KB Output is correct
3 Correct 64 ms 47572 KB Output is correct
4 Correct 394 ms 47628 KB Output is correct
5 Execution timed out 5066 ms 47572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47640 KB Output is correct
2 Correct 61 ms 47636 KB Output is correct
3 Correct 64 ms 47572 KB Output is correct
4 Correct 394 ms 47628 KB Output is correct
5 Execution timed out 5066 ms 47572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 47580 KB Output is correct
2 Execution timed out 5063 ms 47572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 47580 KB Output is correct
2 Execution timed out 5063 ms 47572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 47580 KB Output is correct
2 Execution timed out 5063 ms 47572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47640 KB Output is correct
2 Correct 61 ms 47636 KB Output is correct
3 Correct 64 ms 47572 KB Output is correct
4 Correct 394 ms 47628 KB Output is correct
5 Execution timed out 5066 ms 47572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 47580 KB Output is correct
2 Execution timed out 5063 ms 47572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47640 KB Output is correct
2 Correct 61 ms 47636 KB Output is correct
3 Correct 64 ms 47572 KB Output is correct
4 Correct 394 ms 47628 KB Output is correct
5 Execution timed out 5066 ms 47572 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 47580 KB Output is correct
2 Execution timed out 5063 ms 47572 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 47640 KB Output is correct
2 Correct 61 ms 47636 KB Output is correct
3 Correct 64 ms 47572 KB Output is correct
4 Correct 394 ms 47628 KB Output is correct
5 Execution timed out 5066 ms 47572 KB Time limit exceeded
6 Halted 0 ms 0 KB -