Submission #1167341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167341		uranhishig	Bouquet (EGOI24_bouquet)	C++17	54 / 100	59 ms	6472 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

const int mx = 2e5 + 9;
bool b1 = true;
bool b2 = true;

signed main(){
	int n; cin >> n;
	vector<int> l(n);
	vector<int> r(n);
	cin >> l[0] >> r[0];
	int w;
	if(l[0] != r[0]) {
		b1 = false;
	}
	if(l[0] == r[0]) {
		w = l[0];
	}
	if (r[0] != 0) {
		b2 = false;
	}
	for (int i = 1; i < n; i++) {
		cin >> l[i] >> r[i];
		if (r[i] != 0) {
			b2 = false;
		}
		if (l[i] != r[i]) {
			b1 = false;
		}
		if(l[i] != w) {
			b1 = false;
		}
	}
	int dp[n + 1];
	for (int i = 0; i <= n; i++) {
		dp[i] = 1;
	}
	int ans = 0;
	//subtask 1
	if (b1) {
		cout << (w + n)/(w + 1);
		return 0;
	}
	// subtask 2
	if (b2) {
		vector<int> p;
		p = l;
		sort(p.begin(), p.end());
	}	
	//subtask 3
	if (n <= 1000) {
		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i - l[i]; j++) {
				if (r[j] < i - j) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			ans = max(dp[i], ans);
		}
		cout << ans;
		return 0;
	}
	//subtask 4
	for (int i = 1; i < n; i++) {
		for (int j = max(0ll, i - l[i] - 10) ; j < i - l[i]; j++) {
			if (r[j] < i - j) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(dp[i], ans);
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 0 / 30