Submission #480188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
480188	2021-10-15T07:07:25 Z	NachoLibre	Po (COCI21_po)	C++17	70 / 70	53 ms	6084 KB

Main

#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int)x.size())
using namespace std;

// mt19937 rnd(time(0));
// int R(int l, int r) {
// 	return l + rnd() % (r - l + 1);
// }

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; // n = 5;
	cin >> n;
	vector<int> a(n + 1);
	vector<pair<int, int>> b(n + 1);
	for(int i = 1; i <= n; ++i) {
		// a[i] = R(0, 10);
		cin >> a[i];
		b[i].first = a[i];
		b[i].second = i;
	}
	sort(b.begin() + 1, b.end());
	set<int> s;
	s.insert(n + 1);
	int ans = 0;
	for(int i = 1; i <= n; ) {
		int j = i;
		for(int k = i; k <= n; ++k) {
			if(b[k].first != b[i].first) break;
			j = k;
		}
		if(b[i].first) ++ans;
		for(int k = i + 1; k <= j; ++k) {
			int x = *s.upper_bound(b[k - 1].second);
			int y = *s.upper_bound(b[k].second);
			ans += (x != y);
		}
		for(int k = i; k <= j; ++k) {
			s.insert(b[k].second);
		}
		i = j + 1;
	}
	cout << ans << endl;
	// vector<vector<int>> dp(n + 1, vector<int>(n + 1));
	// for(int z = 0; z < n; ++z) {
	// 	for(int i = 1; i + z <= n; ++i) {
	// 		int j = i + z;
	// 		int mn = 1e9;
	// 		for(int k = i; k <= j; ++k) {
	// 			mn = min(mn, a[k]);
	// 		}
	// 		if(mn) dp[i][j] = 1;
	// 		int w = i;
	// 		for(int k = i; k <= j + 1; ++k) {
	// 			if(a[k] == mn || k == j + 1) {
	// 				if(w < k) {
	// 					dp[i][j] += dp[w][k - 1];
	// 				}
	// 				w = k + 1;
	// 			}
	// 		}
	// 		for(int k = i; k < j; ++k) {
	// 			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
	// 		}
	// 	}
	// }
	// cout << dp[1][n] << endl;
	// for(int i = 1; i <= n; ++i) {
	// 	cout << a[i] << " ";
	// }
	return 0;
}

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	26 ms	3208 KB	Output is correct
5	Correct	37 ms	4684 KB	Output is correct
6	Correct	53 ms	6084 KB	Output is correct
7	Correct	38 ms	6084 KB	Output is correct