oj.uz

Submission #13630

# Submission time Handle Problem Language Result Execution time Memory
13630 2015-02-26T03:10:23 Z gs14004 Mountain Trek Route (IZhO12_route) C++14
95 / 100
 263 ms 13548 KB 
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <utility>
using namespace std;

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

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);
    stack<int> s,t;
    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();
                if(s.top() < a[i%n]){
                    cost[i - t.top() - 1] += s.top() - ptop;
                }
                else{
                    cost[i - t.top() - 1] += a[i%n] - ptop;
                }
            }
            s.push(a[i%n]);
            t.push(i);
        }
    }
    int ret = 0;
    for (int i=1; i<=n; i++) {
       // printf("%d %d\n",i,cost[i]);
        int change = min(cost[i],k/i);
        ret += 2ll * change;
        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 27 ms 9392 KB Output is correct
11 Incorrect 20 ms 9392 KB Output isn't correct
12 Correct 30 ms 9784 KB Output is correct
13 Correct 161 ms 9392 KB Output is correct
14 Correct 228 ms 9392 KB Output is correct
15 Correct 224 ms 9392 KB Output is correct
16 Correct 241 ms 9392 KB Output is correct
17 Correct 210 ms 9392 KB Output is correct
18 Correct 218 ms 9392 KB Output is correct
19 Correct 263 ms 9392 KB Output is correct
20 Correct 172 ms 13548 KB Output is correct