oj.uz

답안 #13627

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13627 2015-02-26T00:59:50 Z gs14004 등산 경로 (IZhO12_route) C++14
15 / 100
 266 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();
            }
        }
    }
    int ret = 0;
    for (int i=1; i<=n; i++) {
        int diff = min(k/i * i,cost[i] * i);
        k -= diff;
        ret += diff / i * 2;
    }
    printf("%d",ret);
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9392 KB Output is correct
2 Correct 0 ms 9392 KB Output is correct
3 Incorrect 0 ms 9392 KB Output isn't 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 0 ms 9392 KB Output isn't correct
9 Incorrect 0 ms 9392 KB Output isn't correct
10 Incorrect 21 ms 9392 KB Output isn't correct
11 Incorrect 22 ms 9392 KB Output isn't correct
12 Incorrect 23 ms 9784 KB Output isn't correct
13 Incorrect 230 ms 9392 KB Output isn't correct
14 Incorrect 266 ms 9392 KB Output isn't correct
15 Incorrect 220 ms 9392 KB Output isn't correct
16 Incorrect 189 ms 9392 KB Output isn't correct
17 Incorrect 196 ms 9392 KB Output isn't correct
18 Incorrect 240 ms 9392 KB Output isn't correct
19 Incorrect 142 ms 9392 KB Output isn't correct
20 Incorrect 173 ms 13548 KB Output isn't correct