oj.uz

Submission #792728

# Submission time Handle Problem Language Result Execution time Memory
792728 2023-07-25T08:21:26 Z 박영우(#10055) Real Mountains (CCO23_day1problem2) C++17
0 / 25
 1 ms 340 KB 
#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;
		if (cnt == 1) {
			ans += H[l] + H[l - 1] + H[l + 1];
			H[l]++;
			continue;
		}
		ans += 1ll * (i + 1) * 2 * (r - l - 1);
		ans += H[l - 1] + H[r + 1];
		ans += min(H[l - 1], H[r + 1]) + i + 1;
		ans += i * (r - l + 1);
		for (j = l; j <= r; j++) H[j]++;
	}
	for (i = 1; i <= N; i++) assert(H[i] == ch[i]);
	cout << ans << ln;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -