oj.uz

Submission #13631

# Submission time Handle Problem Language Result Execution time Memory
13631 2015-02-26T04:24:24 Z gs14004 Mountain Trek Route (IZhO12_route) C++14
95 / 100
 228 ms 13548 KB 
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

int n,k,a[1000005];
int cost[1000005];

stack<int> s,t;

int main(){
    scanf("%d %d",&n,&k);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    int p = (int)(max_element(a,a+n) - a);
    for (int i=p; i<=p+n; i++) {
        if(s.empty() || s.top() >= a[i%n]){
            s.push(a[i%n]);
            t.push(i);
        }
        else{
            while (!s.empty() && s.top() < a[i%n]) {
                int ptop = s.top();
                s.pop();
                t.pop();
                cost[i - t.top() - 1] += min(s.top(),a[i%n]) - ptop;
            }
            s.push(a[i%n]);
            t.push(i);
        }
    }
    int ret = 0;
    for (int i=1; i<=n && i<=k; i++) {
        int change = min(cost[i],k/i);
        ret += change * 2;
        k -= change * i;
    }
    printf("%d",ret);
}

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9392 KB Output is correct
2 Correct 0 ms 9392 KB Output is correct
3 Correct 0 ms 9392 KB Output is correct
4 Correct 0 ms 9392 KB Output is correct
5 Correct 0 ms 9392 KB Output is correct
6 Correct 0 ms 9392 KB Output is correct
7 Correct 0 ms 9392 KB Output is correct
8 Correct 0 ms 9392 KB Output is correct
9 Correct 0 ms 9392 KB Output is correct
10 Correct 20 ms 9392 KB Output is correct
11 Incorrect 27 ms 9392 KB Output isn't correct
12 Correct 0 ms 9784 KB Output is correct
13 Correct 188 ms 9392 KB Output is correct
14 Correct 201 ms 9392 KB Output is correct
15 Correct 207 ms 9392 KB Output is correct
16 Correct 223 ms 9392 KB Output is correct
17 Correct 189 ms 9392 KB Output is correct
18 Correct 228 ms 9392 KB Output is correct
19 Correct 193 ms 9392 KB Output is correct
20 Correct 163 ms 13548 KB Output is correct