Submission #974955

#	Time	Username	Problem	Language	Result	Execution time	Memory
974955		berr	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	8540 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; 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+2; 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75