oj.uz

Submission #974952

# Submission time Handle Problem Language Result Execution time Memory
974952 2024-05-04T07:45:53 Z berr Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 90 ms 134016 KB 
#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N=205, INF=1e18;
int dp[N][N][2][N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, L; cin >> n >> L;

    for(int i=0; i<=n; i++){
        for(int l=0; l<=n; l++){
            for(int j=0; j<2; j++){
                for(int x=0; x<=n; x++){
                    dp[i][l][j][x] = INF;
                }
            }
        }
    }    

    vector<int> x(n), t(n);
    for(auto &i: x) cin >> i;
    for(auto &i: t) cin >> i;


    dp[0][0][0][(t[0]>=x[0])]=dp[0][0][1][(t[0]>=x[0])]=x[0];
    dp[n-1][n-1][0][(t[n-1]>=(L-x[n-1]))]=dp[n-1][n-1][1][(t[n-1]>=(L-x[n-1]))]=L-x[n-1];

    auto val=[&](int a, int b){
        int dis;
        if(a==b) return INF;
        if(b<a) dis=x[b]+L-x[a];
        else dis=x[b]-x[a];

        if(a<b) dis=min(dis, x[a]+L-x[b]);
        else dis=min(dis, x[a]-x[b]);

        return dis;
    };
    auto m=[&](int a){
        a%=n; a+=n; a%=n;
        return a;
    };
    int ans=0;

    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            for(int j=0; j<2; j++){
                for(int x=0; x<=i+1; x++){
                    int r=m(l+i);
                    int v=dp[l][r][j][x];
                    if(v==INF||m(l-1)==r||m(r+1)==l) continue;

                    ans=max(ans, x);

                    int dis=val((j==0?l:r), m(l-1));   
                    int nex=x+((v+dis)<=t[m(l-1)]);
                    ans=max(ans, nex);
                    dp[m(l-1)][r][0][nex]=min(dp[m(l-1)][r][0][nex], v+dis); 

                    dis=val((j==0?l:r), m(r+1));
                    nex=x+((v+dis)<=t[m(r+1)]);
                    ans=max(ans, nex);
                    dp[l][m(r+1)][1][nex]=min(dp[l][m(r+1)][1][nex], v+dis);        
                }
            }
        }
    }

    cout<<ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 63.0

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