Submission #699894

#	Time	Username	Problem	Language	Result	Execution time	Memory
699894		79brue	Tortoise (CEOI21_tortoise)	C++17	0 / 100	1 ms	468 KiB

tortoise

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int cnt, loc, idx;
    dat(){}
    dat(int cnt, int loc, int idx): cnt(cnt), loc(loc), idx(idx){}

    bool operator<(const dat &r)const{
        if(cnt != r.cnt) return cnt < r.cnt;
        if(loc != r.loc) return loc > r.loc;
        return idx > r.idx;
    }
};

int n;
int arr[302], sum[302];
dat DP[603][302][2]; /// 현재 시간, 현재 위치, 손에 든 개수 -> (산 개수, 마지막으로 산 위치)
int ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        sum[i] = sum[i-1];
        if(arr[i] > 0) sum[i] += arr[i];
    }
    for(int i=0; i<=n+n+1; i++) for(int j=0; j<=n; j++){
        DP[i][j][0] = DP[i][j][1] = dat(-1e9, 0, 0);
    }

    DP[0][1][0] = dat(0, 0, 0);
    for(int t=0; t<=n+n+1; t++){
        for(int i=1; i<=n; i++){
            /// 답 갱신
            for(int c=0; c<2; c++) ans = max(ans, DP[t][i][c].cnt);

            /// 제자리에서 연산
            if(arr[i] == -1) DP[t][i][0] = max(DP[t][i][0], DP[t][i][1]);
            if(arr[i] > 0 && i+i-2 >= t && (DP[t][i][0].idx < i || (DP[t][i][0].idx == i && DP[t][i][0].cnt < arr[i]))){
                DP[t][i][1] = max(DP[t][i][1], dat(DP[t][i][0].cnt+1, i, (DP[t][i][0].idx < i) ? 1 : (DP[t][i][0].cnt + 1)));
            }

            /// 좌우 이동
            for(int c=0; c<2; c++){
                DP[t+1][i-1][c] = max(DP[t+1][i-1][c], DP[t][i][c]);
                DP[t+1][i+1][c] = max(DP[t+1][i+1][c], DP[t][i][c]);
            }
        }
    }

    printf("%d", sum[n] - ans);
}

Compilation message (stderr)

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

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