oj.uz

Submission #13629

# Submission time Handle Problem Language Result Execution time Memory
13629 2015-02-26T01:05:12 Z gs14004 Mountain Trek Route (IZhO12_route) C++14
25 / 100
 1412 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 val = 0, ptop = s.top();
                s.pop();
                if(!s.empty() && s.top() < a[i%n]){
                    val = s.top() - ptop;
                }
                else{
                    val = a[i%n] - ptop;
                }
                cost[i - t.top()] += val;
                t.pop();
            }
            s.push(a[i%n]);
            t.push(i);
        }
    }
    int ret = 0;
    for (int i=1; i<=n; i++) {
        while (cost[i] && k >= i) {
            ret += 2;
            k -= i;
            cost[i]--;
        }
    }
    printf("%d",ret);
}

Subtask #1
25.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 Incorrect 0 ms 9392 KB Output isn't correct
6 Incorrect 0 ms 9392 KB Output isn't correct
7 Incorrect 0 ms 9392 KB Output isn't correct
8 Incorrect 13 ms 9392 KB Output isn't correct
9 Incorrect 123 ms 9392 KB Output isn't correct
10 Incorrect 86 ms 9392 KB Output isn't correct
11 Correct 651 ms 9392 KB Output is correct
12 Incorrect 36 ms 9784 KB Output isn't correct
13 Incorrect 797 ms 9392 KB Output isn't correct
14 Incorrect 364 ms 9392 KB Output isn't correct
15 Incorrect 229 ms 9392 KB Output isn't correct
16 Incorrect 256 ms 9392 KB Output isn't correct
17 Incorrect 903 ms 9392 KB Output isn't correct
18 Incorrect 1412 ms 9392 KB Output isn't correct
19 Incorrect 798 ms 9392 KB Output isn't correct
20 Incorrect 473 ms 13548 KB Output isn't correct