oj.uz

Submission #699894

# Submission time Handle Problem Language Result Execution time Memory
699894 2023-02-18T08:10:39 Z 79brue Tortoise (CEOI21_tortoise) C++17
0 / 100
 1 ms 468 KB 
#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

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 27.0

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