Submission #680409

#	Time	Username	Problem	Language	Result	Execution time	Memory
680409		qwerasdfzxcl	Tortoise (CEOI21_tortoise)	C++17	8 / 100	1 ms	312 KiB

tortoise

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int INF = 4e8;
int a[500500];
vector<int> V;

int get_left(int i){
    assert(a[i]!=-1);
    if (i < V[0]) return -INF;
    return (*--lower_bound(V.begin(), V.end(), i)) * 2;
}

int get_right(int i){
    assert(a[i]!=-1);
    if (i > V.back()) return INF;
    return (*lower_bound(V.begin(), V.end(), i)) * 2;
}


int main(){
    int n;
    scanf("%d", &n);

    ll ans = 0;
    for (int i=0;i<n;i++){
        scanf("%d", a+i);
        if (a[i]==-1) V.push_back(i);
        else ans += a[i];
    }

    int s, v = -1, L, R;
    for (int i=0;i<n;i++) if (a[i] > 0){
        v = i*2;
        s = i;
        L = get_left(i);
        R = get_right(i);
        break;
    }
    if (v==-1) {printf("0\n"); return 0;}

    while(true){
        //printf("%d %d %d %d\n", s, v, L, R);
        --a[v/2];
        --ans;

        int nxt = v/2;
        for (;nxt<n;nxt++) if (a[nxt] > 0){
            int D = min(v-L + (nxt*2)-L, R-v + abs(nxt*2-R)) / 2;
            if (s + D > nxt*2) continue;

            s += D;
            if (v!=nxt*2) L = get_left(nxt), R = get_right(nxt);
            v = nxt*2;
            break;
        }
        if (nxt==n) break;
    }

    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tortoise.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27