oj.uz

Submission #211505

# Submission time Handle Problem Language Result Execution time Memory
211505 2020-03-20T15:59:24 Z brcode Collecting Stamps 3 (JOI20_ho_t3) C++14
5 / 100
 204 ms 267256 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long n,l;
long long ans = 0;
const long long MAXN = 210;
long long dp[MAXN][MAXN][MAXN][5];
long long arr[MAXN];
long long t[MAXN];
long long check(long long x){
    x+=(n+1);
    x%=(n+1);
    return x;
}
long long dist(long long from,long long to,long long way){
    if(way == 0){
        if(arr[to]>=arr[from]){
            return arr[to]-arr[from];
        }
        return l-arr[from]+arr[to];
    }else{
        if(arr[from]>=arr[to]){
            return arr[from]-arr[to];
        }
        return arr[from]+l-arr[to];
    }
    
    
}
int main(){
    cin>>n>>l;
    for(long long i=0;i<=n;i++){
        for(long long j=0;j<=n;j++){
            for(long long k=0;k<=n;k++){
                for(long long l=0;l<=4;l++){
                    dp[i][j][k][l] = 1e14;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(long long i=1;i<=n;i++){
        cin>>t[i];
    }
    
    for(long long i=0;i<=n;i++){
        for(long long len=0;len<=n;len++){
            for(long long l=0;l<=n;l++){
                
                long long r=check(l+len);
                if(len == 0 && l==0){
                    r=0;
                }else if(len == 0){
                    continue;
                }
                
                long long currl = dp[i][l][r][0];
                long long currr = dp[i][l][r][1];
                
              //  cout<<len<<" "<<l<<" "<<r<<endl;
                if(currl==1e14 && currr ==1e14){
                    continue;
                }
                ans = max(ans,i);
               // cout<<currl<<" "<<currr<<endl;
                
                if(currl+dist(l,check(r+1),0)<=t[check(r+1)]){
                    dp[i+1][l][check(r+1)][1] = min(dp[i+1][l][check(r+1)][1],currl+dist(l,check(r+1),0));
                   
                }else{
                    dp[i][l][check(r+1)][1] = min(dp[i][l][check(r+1)][1],currl+dist(l,check(r+1),0));
                }
                if(currr+dist(r,check(r+1),0)<=t[check(r+1)]){
                    dp[i+1][l][check(r+1)][1] = min(dp[i+1][l][check(r+1)][1],currr+dist(r,check(r+1),0)); 
                }else{
                    dp[i][l][check(r+1)][1] = min(dp[i+1][l][check(r+1)][1],currr+dist(r,check(r+1),0));
                }
                
                if(currl+dist(l,check(l-1),1)<=t[check(l-1)]){
                    dp[i+1][check(l-1)][r][0]=min(dp[i+1][check(l-1)][r][0],currl+dist(l,check(l-1),1));
                    //cout<<i+1<<" "<<check(l-1)<<" "<<r<<endl;
                }else{
                    dp[i][check(l-1)][r][0]= min(dp[i][check(l-1)][r][0],currl+dist(l,check(l-1),1));
                }
                
                if(currr+dist(r,check(l-1),1)<=t[check(l-1)]){
                    dp[i+1][check(l-1)][r][0] = min(dp[i+1][check(l-1)][r][0],currr+dist(r,check(l-1),1));
                   // cout<<check(l-1)<<" "<<r<<" "<<dp[i+1][check(l-1)][r][0]<<endl;
                }else{
                    dp[i][check(l-1)][r][0] = min(dp[i][check(l-1)][r][0],currr+dist(r,check(l-1),1));
                }
            }
        }
    }
    cout<<ans<<endl;   
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 1152 KB Output is correct
17 Correct 6 ms 1152 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 1152 KB Output is correct
17 Correct 6 ms 1152 KB Output is correct
18 Correct 5 ms 1408 KB Output is correct
19 Incorrect 5 ms 896 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 1152 KB Output is correct
17 Correct 6 ms 1152 KB Output is correct
18 Correct 204 ms 267256 KB Output is correct
19 Correct 109 ms 161784 KB Output is correct
20 Correct 57 ms 83576 KB Output is correct
21 Correct 100 ms 152696 KB Output is correct
22 Correct 130 ms 198264 KB Output is correct
23 Correct 42 ms 68352 KB Output is correct
24 Correct 29 ms 50560 KB Output is correct
25 Correct 42 ms 66664 KB Output is correct
26 Correct 16 ms 20736 KB Output is correct
27 Correct 46 ms 70140 KB Output is correct
28 Correct 28 ms 46080 KB Output is correct
29 Incorrect 46 ms 71928 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 640 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 7 ms 640 KB Output is correct
8 Correct 6 ms 896 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 7 ms 1152 KB Output is correct
13 Correct 5 ms 1152 KB Output is correct
14 Correct 5 ms 640 KB Output is correct
15 Correct 5 ms 640 KB Output is correct
16 Correct 5 ms 1152 KB Output is correct
17 Correct 6 ms 1152 KB Output is correct
18 Correct 5 ms 1408 KB Output is correct
19 Incorrect 5 ms 896 KB Output isn't correct
20 Halted 0 ms 0 KB -