Submission #343118

#	Time	Username	Problem	Language	Result	Execution time	Memory
343118		apostoldaniel854	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	240 ms	26080 KiB

route

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;

const int MAX_N = 1e6;
int a[MAX_N], h[1 + MAX_N];
int stk[1 + MAX_N + 1];


int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int mx = 0;
    for (int i = 0; i < n; i++)
        if (a[mx] < a[i])
            mx = i;
    int nr = 0;
    for (int i = mx; i < n; i++)
        h[nr++] = a[i];
    for (int i = 0; i < mx; i++)
        h[nr++] = a[i];
    h[nr] = a[mx]; /// [0...n] h[0] = h[n] = a[mx]
    int vf = 0;
    priority_queue <pair <int, int>> gaps;
    for (int i = 0; i <= n; i++) {
        while (vf && h[stk[vf]] < h[i]) {
            vf--;
            gaps.push ({-(i - stk[vf] - 1), h[stk[vf + 1]] - min (h[i], h[stk[vf]])});
        }
        stk[++vf] = i;
    }
    int ans = 0;
    ///dbg (n);
    while (gaps.size ()) {
        int length = -gaps.top ().first;
        int heigth = -gaps.top ().second;
      ///  dbg (length);
        gaps.pop ();
        int taken = min (k / length, heigth);
        k -= taken * length;
        ans += taken * 2;
    }
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100