Submission #391277

#	Time	Username	Problem	Language	Result	Execution time	Memory
391277		wildturtle	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	204 ms	258416 KiB

ho_t3

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l,A[202],dp[202][202][4][202],ans,T[202],j;
int main() {
    cin>>n>>l;
    for(ll i=1;i<=n;i++) {
        cin>>A[i];
    }
    for(ll i=1;i<=n;i++) {
        cin>>T[i];
    }
    n++;
    for(ll i=0;i<=n;i++) {
        for(ll j=0;j<=n;j++) {
            for(ll r=0;r<=1;r++) {
                for(ll cnt=0;cnt<=n;cnt++) {
                    dp[i][j][r][cnt]=1e18;
                }
            }
        }
    }
    A[n]=l;
    T[0]=-1;
    dp[0][n][0][0]=0;
    dp[0][n][1][0]=0;
    ans=0;
    for(ll sz=n-1;sz>=1;sz--) {
        for(ll i=0;i+sz<=n;i++) {
            j=i+sz;
            for(ll cnt=0;cnt<=n;cnt++) {
                if(i!=0) dp[i][j][0][cnt]=min(dp[i][j][0][cnt],dp[i-1][j][0][cnt]+A[i]-A[i-1]);
                if(j!=n) dp[i][j][1][cnt]=min(dp[i][j][1][cnt],dp[i][j+1][1][cnt]+A[j+1]-A[j]);
                if(cnt!=0) {
                    if(i!=0 && T[i]>=dp[i-1][j][0][cnt-1]+A[i]-A[i-1])
                    dp[i][j][0][cnt]=min(dp[i][j][0][cnt],dp[i-1][j][0][cnt-1]+A[i]-A[i-1]);
                    if(j!=n && T[j]>=dp[i][j+1][1][cnt-1]+A[j+1]-A[j]) 
                    dp[i][j][1][cnt]=min(dp[i][j][1][cnt],dp[i][j+1][1][cnt-1]+A[j+1]-A[j]);
                }
                dp[i][j][0][cnt]=min(dp[i][j][0][cnt],dp[i][j][1][cnt]+l-A[j]+A[i]);
                dp[i][j][1][cnt]=min(dp[i][j][1][cnt],dp[i][j][0][cnt]+l-A[j]+A[i]);
                if(dp[i][j][0][cnt]!=1e18 || dp[i][j][1][cnt]!=1e18) ans=max(ans,cnt);
            }
        }
    }
    cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75