oj.uz

답안 #393604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
393604 2021-04-24T05:36:40 Z 79brue Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 1100 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n; ll l;
ll arr[205], t[205];
ll DP[205][205][205][2]; /// l에 있는 경우 = 0, r에 있는 경우 = 1
int ans;

int main(){
    scanf("%d %lld", &n, &l);
    for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
    for(int i=1; i<=n; i++) scanf("%lld", &t[i]);
    arr[n+1] = l;

    for(int i=0; i<=n+3; i++) for(int j=0; j<=n+3; j++) for(int k=0; k<=n+3; k++) DP[i][j][k][0] = DP[i][j][k][1] = 1e18;
    DP[0][n+1][0][0] = DP[0][n+1][0][1] = 0;

    for(int d=n+1; d>=0; d--){
        for(int i=0; i<=n+1-d; i++){
            int j = i+d;
            for(int p=0; p<=n; p++){
                ll newT; int newP;
                if(DP[i][j][p][0] < 1e18){ /// 현재 i에 있는 경우
                    ans = max(ans, p);
                    if(d){
                        newT = DP[i][j][p][0] + (arr[i+1] - arr[i]);
                        newP = p + (newT <= t[i+1]);
                        DP[i+1][j][newP][0] = min(DP[i+1][j][newP][0], newT);

                        newT = DP[i][j][p][0] + l - (arr[j-1] - arr[i]);
                        newP = p + (newT <= t[j-1]);
                        DP[i][j-1][newP][1] = min(DP[i][j-1][newP][1], newT);
                    }
                }

                if(DP[i][j][p][1] < 1e18){
                    ans = max(ans, p);
                    if(d){
                        newT = DP[i][j][p][1] + l - (arr[j] - arr[i+1]);
                        newP = p + (newT <= t[i+1]);
                        DP[i+1][j][newP][0] = min(DP[i+1][j][newP][0], newT);

                        newT = DP[i][j][p][1] + (arr[j] - arr[j-1]);
                        newP = p + (newT <= t[j-1]);
                        DP[i][j-1][newP][1] = min(DP[i][j-1][newP][1], newT);
                    }
                }
            }
        }
    }

    printf("%d", ans);
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     scanf("%d %lld", &n, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
ho_t3.cpp:14:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |     for(int i=1; i<=n; i++) scanf("%lld", &t[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 940 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 1068 KB Output is correct
13 Correct 1 ms 1072 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Incorrect 1 ms 1068 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 940 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 1068 KB Output is correct
13 Correct 1 ms 1072 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Incorrect 1 ms 1068 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 940 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 1068 KB Output is correct
13 Correct 1 ms 1072 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Incorrect 1 ms 1068 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 940 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 1068 KB Output is correct
13 Correct 1 ms 1072 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct
16 Incorrect 1 ms 1068 KB Output isn't correct
17 Halted 0 ms 0 KB -