제출 #1315994

#제출 시각아이디문제언어결과실행 시간메모리
1315994bahaktlCollecting Stamps 3 (JOI20_ho_t3)C++20
5 / 100
87 ms160088 KiB
#include <bits/stdc++.h>

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

const int N=310;
const int inf=8e18;
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]=dp[i][j][1][k]=inf;
                }
            }
        }
        dp[n + 1][0][1][0]=dp[n + 1][0][0][0]=0;
        for(int j=0;j<=n;j++) {
            for(int i=n + 1;i > j;i--) {
                for(int k=0;k<=n;k++) {
                    if(i<=n) {
                        dp[i][j][0][k] = min(dp[i][j][0][k], dp[i + 1][j][0][k] + x[i + 1] - x[i]);
                        if(k > 0 && dp[i+1][j][0][k-1]<inf && dp[i+1][j][0][k-1]+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]+x[i + 1]-x[i]);
                        }

                        dp[i][j][0][k] = min(dp[i][j][0][k], dp[i + 1][j][1][k] + l-x[i]+x[j]);
                        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]);
                        }
                    }
                    if(j>0) {
                        dp[i][j][1][k] = min(dp[i][j][1][k], dp[i][j - 1][1][k] + x[j] - x[j - 1]);
                        if(k > 0 && dp[i][j-1][1][k-1]<inf && dp[i][j-1][1][k-1]+x[j]-x[j-1]<=t[j]) {
                                dp[i][j][1][k]=min(dp[i][j][1][k], dp[i][j-1][1][k-1]+x[j]-x[j-1]);
                        }

                        dp[i][j][1][k] = min(dp[i][j][1][k], dp[i][j - 1][0][k] + l-x[i]+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] /*<---Тут была ошибка вместо t[j] ты написал t[i]*/ ) {
                                dp[i][j][1][k]=min(dp[i][j][0][k],dp[i][j-1][0][k-1]+l-x[i]+x[j]);
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=n + 1;i>=1;i--) {
            for(int j=0;j<i;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);
                        // 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...