Submission #489270

#	Time	Username	Problem	Language	Result	Execution time	Memory
489270		SirCovidThe19th	등산 경로 (IZhO12_route)	C++17	100 / 100	464 ms	12604 KiB

route

#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 / 100