제출 #680433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680433		qwerasdfzxcl	Tortoise (CEOI21_tortoise)	C++17	48 / 100	569 ms	327864 KiB

tortoise

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
constexpr int INF = 1e4;
struct Vertex{
    int v, now, tot, p, on, tor;
    Vertex(){}
    Vertex(int _v, int _n, int _tot, int _p, int _on, int _tor): v(_v), now(_n), tot(_tot), p(_p), on(_on), tor(_tor) {}
    bool operator < (const Vertex &V) const{return tor > V.tor;}
};
int a[500500], L[500500], R[500500], nxt[500500];
short dist[303][303][303][3][2];
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));
}

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


int main(){
    int n, s = INF;
    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], s = min(s, i);
    }
    if (s==INF) {printf("0\n"); return 0;}

    ///init
    int prv = -1;
    for (int i=0;i<n;i++) if (a[i]!=-1){
        L[i] = get_left(i), R[i] = get_right(i);
        nxt[i] = INF;
        //printf("%d -> %d %d %d\n", i, L[i], R[i], nxt[i]);
        if (prv!=-1) nxt[prv] = i;
        prv = i;
    }

    for (int i=0;i<303;i++){
        for (int j=0;j<303;j++){
            for (int k=0;k<303;k++){
                for (int l=0;l<3;l++){
                    for (int z=0;z<2;z++) dist[i][j][k][l][z] = INF;
                }
            }
        }
    }

    priority_queue<Vertex> pq;
    dist[s][0][0][0][0] = s;
    pq.emplace(s, 0, 0, 0, 0, s);


    int rans = 0;
    while(!pq.empty()){
        auto [v, now, tot, p, on, tor] = pq.top(); pq.pop();
        if (dist[v][now][tot][p][on] != tor) continue;

        //printf("%d %d %d %d %d -> %d\n", v, now, tot, p, on, tor);
        rans = max(rans, tot);

        int nv = nxt[v], rv = v;
        if (p==1) rv = L[v];
        if (p==2) rv = R[v];
        if (nv!=INF && dist[nv][0][tot][0][on] > tor + abs(nv-rv)){
            dist[nv][0][tot][0][on] = tor + abs(nv-rv);
            pq.emplace(nv, 0, tot, 0, on, tor + abs(nv-rv));
        }


        if (!on){
            if (p==0){
                if (now < a[v] && tor <= v*2){
                    if (dist[v][now+1][tot+1][0][1] > tor){
                        dist[v][now+1][tot+1][0][1] = tor;
                        pq.emplace(v, now+1, tot+1, 0, 1, tor);
                    }
                }
            }

            else{
                if (dist[v][now][tot][0][0] > tor + abs(rv-v)){
                    dist[v][now][tot][0][0] = tor + abs(rv-v);
                    pq.emplace(v, now, tot, 0, 0, tor + abs(rv-v));
                }
            }
        }
        else{
            if (p==0){
                if (dist[v][now][tot][1][1] > tor + abs(L[v]-v)){
                    dist[v][now][tot][1][1] = tor + abs(L[v]-v);
                    pq.emplace(v, now, tot, 1, 1, tor + abs(L[v]-v));
                }
                if (dist[v][now][tot][2][1] > tor + abs(R[v]-v)){
                    dist[v][now][tot][2][1] = tor + abs(R[v]-v);
                    pq.emplace(v, now, tot, 2, 1, tor + abs(R[v]-v));
                }
            }
            else{
                if (dist[v][now][tot][p][0] > tor){
                    dist[v][now][tot][p][0] = tor;
                    pq.emplace(v, now, tot, p, 0, tor);
                }
            }
        }


    }

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

컴파일 시 표준 에러 (stderr) 메시지

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

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