oj.uz

Submission #489270

# Submission time Handle Problem Language Result Execution time Memory
489270 2021-11-21T20:41:11 Z SirCovidThe19th Mountain Trek Route (IZhO12_route) C++17
100 / 100
 464 ms 12604 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e6 + 5;

int n, k, A[mx], ans; priority_queue<pair<int, int>> pq; stack<int> stk; 

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> A[i];
        while (!stk.empty() and A[stk.top()] <= A[i]) stk.pop();
        stk.push(i);
    }
    for (int i = 1; i <= n; i++){
        int mxTop = 0;
        while (!stk.empty()){
            int L = stk.top();
			int dst = (L < i) ? (i - L - 1) : (n - (L - i + 1));
			if (dst) pq.push({-dst, min(A[L], A[i]) - mxTop});
            if (A[L] > A[i]) break;
            mxTop = max(mxTop, A[L]); stk.pop();
        }
        stk.push(i);
    }
	while (!pq.empty()){
		pair<int, int> cur = pq.top(); pq.pop(); 
		int use = min(k / -cur.first, cur.second);
		ans += 2 * use; k -= use * -cur.first; 
	}
    cout<<ans<<endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 42 ms 1832 KB Output is correct
11 Correct 53 ms 1816 KB Output is correct
12 Correct 45 ms 1720 KB Output is correct
13 Correct 436 ms 12508 KB Output is correct
14 Correct 464 ms 12468 KB Output is correct
15 Correct 385 ms 12512 KB Output is correct
16 Correct 417 ms 12548 KB Output is correct
17 Correct 409 ms 12536 KB Output is correct
18 Correct 437 ms 12604 KB Output is correct
19 Correct 440 ms 12428 KB Output is correct
20 Correct 364 ms 12452 KB Output is correct