Submission #202331

#	Time	Username	Problem	Language	Result	Execution time	Memory
202331		giorgikob	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	119 ms	128892 KiB

ho_t3

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6 + 69;

int n,k,l,r,ans;
ll dro,x,L;

ll A[N],T[N];

ll dp[202][202][202][2];

ll dist(ll x,ll y){
    return min(abs(x-y),L-abs(x-y));
}

int main(){

    cin>>n>>L;

    for(int i=1;i<=n;i++){
        cin>>A[i];
    }

    A[n+1] = L;

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

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                for(int t=0;t<=1;t++)
                    dp[i][j][k][t] = 1e18;
            }
        }
    }




    dp[0][0][0][1] = dp[0][0][0][0] = 0;

    for(int i=0;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            for(int k=0;k<=i+j;k++){

                x = dp[i][j][k][0];
                if(x<1e18){
                    ans = max(k,ans);
                }

                dro = x + dist(A[i+1], A[i]);
                dp[i+1][j][k+(dro<=T[i+1])][0] = min(dp[i+1][j][k+(dro<=T[i+1])][0],dro);

                dro = x + dist(A[i], A[n-j]);
                dp[i][j+1][k+(dro<=T[n-j])][1] = min(dp[i][j+1][k+(dro<=T[n-j])][1],dro);

                x = dp[i][j][k][1];
                if(x<1e18){
                    ans = max(k,ans);
                }

                dro = x + dist( A[i+1], A[n+1-j]);
                dp[i+1][j][k+(dro<=T[i+1])][0] = min(dp[i+1][j][k+(dro<=T[i+1])][0],dro);

                dro = x + dist(A[n+1-j],A[n-j]);
                dp[i][j+1][k+(dro<=T[n-j])][1] = min(dp[i][j+1][k+(dro<=T[n-j])][1],dro);

            }
        }
    }

    cout<<ans<<endl;
}

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