#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#define MAXS 500
#define INF 1000000020
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N;
int H[MAX];
int ch[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N;
int i, j;
int mv = 1;
for (i = 1; i <= N; i++) cin >> H[i];
for (i = 1; i <= N; i++) ch[i] = H[i];
for (i = 1; i <= N; i++) if (H[mv] < H[i]) mv = i;
for (i = 1; i <= mv; i++) ch[i] = max(ch[i], ch[i - 1]);
for (i = N; i >= mv; i--) ch[i] = max(ch[i], ch[i + 1]);
ll ans = 0;
for (i = 0; i <= 110; i++) {
int l, r;
l = r = -1;
int cnt = 0;
for (j = 1; j <= N; j++) {
if (H[j] != i) continue;
if (ch[j] == H[j]) continue;
cnt++;
if (!~l) l = j;
r = j;
}
if (!cnt) continue;
int lmn = INF;
int rmn = INF;
for (j = 1; j < l; j++) if (H[j] > i) lmn = min(lmn, H[j]);
for (j = r + 1; j <= N; j++) if (H[j] > i) rmn = min(rmn, H[j]);
int mn = INF;
for (j = 1; j <= N; j++) if (H[j] > i) mn = min(mn, H[j]);
if (l == r) {
ans += 0ll + i + lmn + rmn;
H[l]++;
continue;
}
ans += 0ll + lmn + rmn + mn;
ans += 1ll * i * cnt;
ans += 1ll * (2ll * cnt - 3) * (i + 1ll);
for (j = l; j <= r; j++) if (H[j] == i) H[j]++;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |