oj.uz

답안 #38313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38313 2018-01-03T15:49:13 Z romanasa 등산 경로 (IZhO12_route) C++14
100 / 100
 346 ms 26416 KB 
#include <bits/stdc++.h>
#define err(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

typedef long long ll;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > S;

#define TASK "g"

int main() {	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	rotate(a.begin(), max_element(a.begin(), a.end()), a.end());
	a.push_back(a[0]);
	
	vector<int> s;
	for (int i = 0; i <= n; i++) {
  		while (s.size() && a[s.back()] < a[i]) {
  			int val = a[s.back()];
  			s.pop_back();
  			S.push({ (i - s.back() - 1), min(a[s.back()], a[i]) - val });
  		}
		s.push_back(i);
	}
	
	int ans = 0;
	while (S.size()) {
		auto c = S.top();
		S.pop();
	
		int t = min(k / c.first, c.second);
		ans += t * 2;
		k -= t * c.first;
	}
	cout << ans << "\n";

	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2176 KB Output is correct
2 Correct 0 ms 2176 KB Output is correct
3 Correct 0 ms 2176 KB Output is correct
4 Correct 0 ms 2176 KB Output is correct
5 Correct 0 ms 2176 KB Output is correct
6 Correct 0 ms 2176 KB Output is correct
7 Correct 0 ms 2176 KB Output is correct
8 Correct 0 ms 2176 KB Output is correct
9 Correct 0 ms 2176 KB Output is correct
10 Correct 19 ms 5048 KB Output is correct
11 Correct 36 ms 5048 KB Output is correct
12 Correct 23 ms 5304 KB Output is correct
13 Correct 303 ms 26416 KB Output is correct
14 Correct 346 ms 26416 KB Output is correct
15 Correct 253 ms 26416 KB Output is correct
16 Correct 283 ms 26416 KB Output is correct
17 Correct 293 ms 26416 KB Output is correct
18 Correct 333 ms 26416 KB Output is correct
19 Correct 243 ms 26416 KB Output is correct
20 Correct 299 ms 26416 KB Output is correct