Submission #1316378

#TimeUsernameProblemLanguageResultExecution timeMemory
1316378bahaktlCollecting Stamps 3 (JOI20_ho_t3)C++20
100 / 100
121 ms199296 KiB
#include <bits/stdc++.h>

#define int long long 
#define pb push_back
using namespace std;

const int N=310;
const int inf=1e18;
const int mod=1e9+7;

int x[N],t[N];
int dp[N][N][2][N];

signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T=1;
    // cin>>T;
    while(T--) {
        int n,l;
        cin>>n>>l;
        for(int i=1;i<=n;i++) cin>>x[i];
        for(int i=1;i<=n;i++) cin>>t[i];
        x[n+1] = l;
        for(int i=0;i<=n+1;i++) {
            for(int j=0;j<=n+1;j++) {
                for(int k=0;k<=n;k++) {
                    dp[i][j][0][k]=inf;
                    dp[i][j][1][k]=inf;
                }
            }
        }
        dp[n + 1][0][1][0]=dp[n + 1][0][0][0]=0;
        for(int i=n+1;i>0;i--) {
            for(int j=0;j<i;j++) {
                for(int k=0;k<=n;k++) {
                    if(i<=n) {
                        if(k > 0 && dp[i+1][j][0][k-1]<inf && dp[i+1][j][0][k-1]+abs(x[i + 1]-x[i])<=t[i]) {
                            dp[i][j][0][k]=min(dp[i][j][0][k], dp[i+1][j][0][k-1]+abs(x[i + 1]-x[i]));
                        }
                        dp[i][j][0][k] = min({inf, dp[i][j][0][k], dp[i + 1][j][0][k] + abs(x[i + 1]-x[i])});
                        if(k > 0 && dp[i+1][j][1][k-1]<inf && dp[i+1][j][1][k-1]+l-x[i]+x[j]<=t[i]) {
                            dp[i][j][0][k]=min(dp[i][j][0][k],dp[i+1][j][1][k-1]+l-x[i]+x[j]);
                        }
                        dp[i][j][0][k] = min({inf, dp[i][j][0][k], dp[i + 1][j][1][k] + l-x[i]+x[j]});
                    }
                    if(j>0) {
                        if(k > 0 && dp[i][j-1][1][k-1]<inf && dp[i][j-1][1][k-1]+abs(x[j - 1]-x[j])<=t[j]) {
                            dp[i][j][1][k]=min(dp[i][j][1][k], dp[i][j-1][1][k-1]+abs(x[j - 1]-x[j]));
                        }
                        dp[i][j][1][k] = min({inf, dp[i][j][1][k], dp[i][j - 1][1][k] + abs(x[j - 1]-x[j])});
                        if(k > 0 && dp[i][j-1][0][k-1]<inf && dp[i][j-1][0][k-1]+l-x[i]+x[j]<=t[j]) {
                            dp[i][j][1][k]=min(dp[i][j][1][k],dp[i][j-1][0][k-1]+l-x[i]+x[j]);
                        }
                        dp[i][j][1][k] = min({inf, dp[i][j][1][k], dp[i][j - 1][0][k] + l-x[i]+x[j]});
                    }
                }
            }
        }
        // cout<<dp[5][3][1][4]<<'\n';
        int ans=0;
        for(int i=n+1;i>=0;i--) {
            for(int j=0;j<=n+1;j++) {
                for(int k=1;k<=n;k++) {
                    if(dp[i][j][0][k]<inf || dp[i][j][1][k]<inf) {
                        ans=max(ans,k);
                        //if(k==5)cout<<i<<' '<<j<<"\n";
                    }
                }
            }
        }
        cout<<ans;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...