oj.uz

Submission #548481

# Submission time Handle Problem Language Result Execution time Memory
548481 2022-04-13T14:04:19 Z krit3379 Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 1 ms 980 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 205

int x[N],rev[N],t[N],ans;
long long dp[2][N][N][N];

int main(){
    int n,m,l,i,j,k;
    scanf("%d %d",&n,&l);
    for(i=1;i<=n;i++)scanf("%d",&x[i]),rev[i]=l-x[i];
    for(i=1;i<=n;i++)scanf("%d",&t[i]);
    for(i=0;i<=n+1;i++)for(j=0;j<=n+1;j++)for(k=0;k<=n+1;k++)dp[0][i][j][k]=dp[1][i][j][k]=1e18;
    dp[1][0][0][0]=dp[0][0][n+1][0]=0;
    
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            if(i&&j&&dp[1][i-1][0][j-1]+x[j]-x[j-1]<=t[j]){
                dp[1][i][0][j]=min(dp[1][i][0][j],dp[1][i-1][0][j-1]+x[j]-x[j-1]);
            }
            if(j)dp[1][i][0][j]=min(dp[1][i][0][j],dp[1][i][0][j-1]+x[j]-x[j-1]);
        }
    }
    
    for(i=0;i<=n;i++){
        for(j=n+1;j>0;j--){
            if(i&&j<=n&&dp[0][i-1][j+1][0]+rev[j]-rev[j+1]<=t[j]){
                dp[0][i][j][0]=min(dp[0][i][j][0],dp[0][i-1][j+1][0]+rev[j]-rev[j+1]);
            }
            if(j<=n)dp[0][i][j][0]=min(dp[0][i][j][0],dp[0][i][j+1][0]+rev[j]-rev[j+1]);
        }
    }
    for(i=0;i<=n;i++){
        for(j=n+1;j>=0;j--){
            for(k=0;k<=n+1;k++){
                if(i){
                    if(j&&j<=n&&dp[0][i-1][j+1][k]+rev[j]-rev[j+1]<=t[j])dp[0][i][j][k]=min(dp[0][i][j][k],dp[0][i-1][j+1][k]+rev[j]-rev[j+1]);
                    if(j&&j<=n&&dp[1][i-1][j+1][k]+rev[j]+x[k]<=t[j])dp[0][i][j][k]=min(dp[0][i][j][k],dp[1][i-1][j+1][k]+rev[j]+x[k]);
                    if(k&&k<=n&&dp[1][i-1][j][k-1]+x[k]-x[k-1]<=t[k])dp[1][i][j][k]=min(dp[1][i][j][k],dp[1][i-1][j][k-1]+x[k]-x[k-1]);
                    if(k&&k<=n&&dp[0][i-1][j][k-1]+x[k]+rev[j]<=t[k])dp[1][i][j][k]=min(dp[1][i][j][k],dp[0][i-1][j][k-1]+x[k]+rev[j]);
                }
                if(j&&j<=n)dp[0][i][j][k]=min({dp[0][i][j][k],dp[0][i][j+1][k]+rev[j]-rev[j+1],dp[1][i][j+1][k]+rev[j]+x[k]});
                if(k&&k<=n)dp[1][i][j][k]=min({dp[1][i][j][k],dp[1][i][j][k-1]+x[k]-x[k-1],dp[0][i][j][k-1]+rev[j]+x[k]});
                if(dp[0][i][j][k]<1e18||dp[1][i][j][k]<1e18)ans=max(ans,i);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:9:11: warning: unused variable 'm' [-Wunused-variable]
    9 |     int n,m,l,i,j,k;
      |           ^
ho_t3.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:11:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for(i=1;i<=n;i++)scanf("%d",&x[i]),rev[i]=l-x[i];
      |                      ~~~~~^~~~~~~~~~~~
ho_t3.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(i=1;i<=n;i++)scanf("%d",&t[i]);
      |                      ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 820 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 820 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 820 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 820 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Incorrect 1 ms 980 KB Output isn't correct
17 Halted 0 ms 0 KB -