#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;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
