Submission #974956

#	Time	Username	Problem	Language	Result	Execution time	Memory
974956		berr	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	105 ms	134008 KiB

ho_t3

#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+1; i++){
        for(int l=0; l<=n+1; l++){
            for(int j=0; j<2; j++){
                for(int x=0; x<=n+1; 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=max(t[0]>=x[0], t[n-1]>=(L-x[n-1]));

    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++){
                    int r=m(l+i);
                    int v=dp[l][r][j][x];
                    if(v==INF||m(l-1)==r||m(r+1)==l) continue;


                    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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75