oj.uz

Submission #1113881

# Submission time Handle Problem Language Result Execution time Memory
1113881 2024-11-17T17:29:31 Z Tsagana Mountain Trek Route (IZhO12_route) C++14
100 / 100
 180 ms 28420 KB 
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

void solve () {
	int n, k; cin >> n >> k;
	
	vector<int>a(n);
	for (auto &i: a) cin >> i;	
	rotate(a.begin(), max_element(all(a)), a.end());
	a.pb(a[0]);
	
	pq<pair<int, int>> q;
	vector<int> s;

	for (int i = 0; i <= n; i++) {
  		while (s.size() && a[s.back()] < a[i]) {
  			int val = a[s.back()];
  			s.pp();
  			q.push({s.back()+1-i, min(a[s.back()], a[i])-val});
  		}
		s.pb(i);
	}

	int ans = 0;
	while (!q.empty()){
		pair<int, int> i = q.top(); q.pop();
		i.F *= -1;
		int l = min(k/i.F, i.S);
		ans += l*2;
		k -= l*i.F;
	}
	cout << ans;
}
int main() {IOS solve(); return 0;}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 18 ms 3016 KB Output is correct
11 Correct 24 ms 3272 KB Output is correct
12 Correct 18 ms 3260 KB Output is correct
13 Correct 172 ms 28420 KB Output is correct
14 Correct 180 ms 28420 KB Output is correct
15 Correct 163 ms 26452 KB Output is correct
16 Correct 177 ms 27396 KB Output is correct
17 Correct 169 ms 27404 KB Output is correct
18 Correct 173 ms 28100 KB Output is correct
19 Correct 174 ms 28420 KB Output is correct
20 Correct 146 ms 24772 KB Output is correct