Submission #844727

#	Time	Username	Problem	Language	Result	Execution time	Memory
844727		anton	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	58 ms	129880 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
const int INF = 1e18;
const int MAX_N = 202;

int N, L;
int X[MAX_N], T[MAX_N];
pii dp[MAX_N][MAX_N][MAX_N];

int dist(int a, int b){
    if(a>b){
        return (b-a+L)%L;
    }
    return a-b;
}

void push_val(int left, int right, int has){
    int sz = dist(X[left],X[right]);
    dp[left][right][has].first = min(dp[left][right][has].first, dp[left][right][has].second+sz);
    dp[left][right][has].second = min(dp[left][right][has].second, dp[left][right][has].first+sz);

    if(left-right>1){
        int new_time = dp[left][right][has].first + abs(X[left-1] - X[left]);
        if(new_time<=T[left-1]){
            dp[left-1][right][has+1].first = min(dp[left-1][right][has+1].first , new_time);
        }
        else{
            dp[left-1][right][has].first = min(dp[left-1][right][has].first , new_time);
        }

        new_time = dp[left][right][has].second + abs(X[right+1] - X[right]);
        if(new_time<=T[right+1]){
            dp[left][right+1][has+1].second = min(dp[left][right+1][has+1].second , new_time);
        }
        else{
            dp[left][right+1][has].second = min(dp[left][right+1][has].second , new_time);
        }
    }
}


signed main(){
    fill(&dp[0][0][0], &dp[MAX_N-1][MAX_N-1][MAX_N-1] +1, pii(INF, INF));
    cin>>N>>L;

    N++;

    X[0]= 0;
    T[0] = -1;

    for(int i = 1; i<N; i++){
        cin>>X[i];
    }
    for(int i =1; i<N; i++){
        cin>>T[i];
    }

    X[N] = L;
    T[N] = -1;

    dp[N][0][0] = pii(0, 0);

    for(int l = N; l>0; l--){
        for(int r = 0; r<l; r++){
            for(int has = 0; has<N; has++){
                push_val(l, r, has);
                //cout<<l<<" "<<r<<" "<<has<<" "<<dp[l][r][has].first<<" "<<dp[l][r][has].second<<endl;
            }
        }
    }

    int res =0;
    for(int l = N; l>0; l--){
        for(int r = 0; r<l; r++){
            for(int has = 0; has<N; has++){
                if(dp[l][r][has].first<INF || dp[l][r][has].second<INF){
                    res = max(res, has);
                }
            }
        }
    }

    cout<<res<<endl;
}

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