oj.uz

Submission #131500

# Submission time Handle Problem Language Result Execution time Memory
131500 2019-07-17T08:22:02 Z 송준혁(#3182) Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 380 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;

int N, K;
LL A[101010];
LL P, ans;

priority_queue<pii> LPQ, RPQ;
LL LS, RS;

bool chk(LL k){
    int l=K, r=K, ql=K, qr=K;
    LS = RS = 0;
    while (!LPQ.empty()) LPQ.pop();
    while (!RPQ.empty()) RPQ.pop();
    LPQ.push(pii(0, K));
    k *= 2;
    LL H=P*k;
    while (!LPQ.empty() || !RPQ.empty()){
        pii T;
        if (LPQ.empty()) T = RPQ.top(), RPQ.pop();
        else if (RPQ.empty()) T = LPQ.top(), LPQ.pop();
        else {
            if (LPQ.top().first - LS > RPQ.top().first - RS) T = LPQ.top(), LPQ.pop();
            else T = RPQ.top(), RPQ.pop();
        }
        if (l <= T.second && T.second <= r && T.second != K) continue;

        if (T.second > K){
            T.first -= RS, H += T.first;
            LL x=0, y=0;
            for (; r<T.second; r++){
                y -= A[r+1]-A[r];
                x = max(x, -y);
                if (x > H) return false;
                y += P*k;
            }
            if (H < 0) return false;
            RS += T.first;
        }
        if (T.second < K){
            T.first -= LS, H += T.first;
            LL x=0, y=0;
            for (; l>T.second; l--){
                y -= A[l]-A[l-1];
                x = max(x, -y);
                if (x > H) return false;
                y += P*k;
            }
            if (H < 0) return false;
            LS += T.first, l = T.second;
        }
        LL x=0, y=0;
        for (int t=ql-1; t>0; t--){
            y -= A[t+1]-A[t];
            x = max(x, -y);
            if (x > H) break;
            y += P*k;
            LPQ.push(pii(y+LS, t));
            ql = t;
        }
        x=0, y=0;
        for (int t=qr+1; t<=N; t++){
            y -= A[t]-A[t-1];
            x = max(x, -y);
            if (x > H) break;
            y += P*k;
            RPQ.push(pii(y+RS, t));
            qr = t;
        }
    }
    if (l > 1 || r < N) return false;
    return true;
}

int main(){
    scanf("%d %d %lld", &N, &K, &P);
    for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
    if (A[1] == A[N]){
        puts("0");
        return 0;
    }
    LL L = 1, R = 1000000000;
    while (L <= R){
        LL mid = (L+R)/2;
        if (chk(mid)) R = mid-1, ans = mid;
        else L = mid+1;
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld", &N, &K, &P);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:80:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
                              ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -