Submission #489585

#	Time	Username	Problem	Language	Result	Execution time	Memory
489585		Jarif_Rahman	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	132 ms	126280 KiB

ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
ll dp[200][200][2][201];
const ll inf = 1e9+7;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for(int i = 0; i < 200; i++) for(int j = 0; j < 200; j++) for(int k = 0; k <= 200; k++){
        dp[i][j][0][k] = -inf;
        dp[i][j][1][k] = -inf;
    }

    int n; ll L; cin >> n >> L;

    vector<ll> dis(n), tm(n);
    for(ll &x: dis) cin >> x;
    for(ll &x: tm) cin >> x;

    for(int i = 0; i < n; i++){
        dp[i][i][0][1] = tm[i];
        dp[i][i][1][1] = tm[i];
    }

    for(int rr = 2; rr <= n; rr++) for(int l = 0; l+rr-1 < n; l++){
        int r = l+rr-1;

        vector<ll> cur0(n+1), cur1(n+1);
        
        // left -> right
        for(int i = 1; i <= n; i++) cur0[i] = dp[l+1][r][0][i]-(dis[l+1]-dis[l]);
        for(int i = 1; i <= n; i++){
            if(tm[l] > cur0[i]){
                for(int j = n; j > i; j--) cur0[j] = cur0[j-1];
                cur0[i] = tm[l];
                break;
            }
        }

        // left -> left
        for(int i = 1; i <= n; i++) cur1[i] = dp[l+1][r][1][i]-(dis[l]+L-dis[r]);
        for(int i = 1; i <= n; i++){
            if(tm[l] > cur1[i]){
                for(int j = n; j > i; j--) cur1[j] = cur1[j-1];
                cur1[i] = tm[l];
                break;
            }
        }


        // left
        for(int i = 1; i <= n; i++) dp[l][r][0][i] = max(cur0[i], cur1[i]);

        // right -> right
        for(int i = 1; i <= n; i++) cur1[i] = dp[l][r-1][0][i]-(L-dis[r]+dis[l]);
        for(int i = 1; i <= n; i++){
            if(tm[r] > cur1[i]){
                for(int j = n; j > i; j--) cur1[j] = cur1[j-1];
                cur1[i] = tm[r];
                break;
            }
        }

        // right -> left
        for(int i = 1; i <= n; i++) cur0[i] = dp[l][r-1][1][i]-(dis[r]-dis[r-1]);
        for(int i = 1; i <= n; i++){
            if(tm[r] > cur0[i]){
                for(int j = n; j > i; j--) cur0[j] = cur0[j-1];
                cur0[i] = tm[r];
                break;
            }
        }

        // right
        for(int i = 1; i <= n; i++) dp[l][r][1][i] = max(cur0[i], cur1[i]);
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(dp[0][n-1][0][i] >= dis[0] || dp[0][n-1][1][i] >= L-dis[n-1]) ans = i;
    }
    cout << ans << "\n";
}

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