Submission #1213867

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213867		Hamed_Ghaffari	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	98 ms	128584 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define mins(a, b) (a = min(a, b))

const int MXN = 203;
const ll  inf = 1e12;

int n, L, X[MXN], T[MXN];
ll dp[MXN][MXN][MXN][2];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> X[i];
    X[n+1] = L;
    for(int i=1; i<=n; i++) cin >> T[i];
    for(int i=0; i<=n; i++)
        for(int j=0; i+j<=n; j++)
            for(int k=0; k<=i+j; k++)
                dp[k][i][j][0] = dp[k][i][j][1] = inf;
    dp[0][0][0][0] = 0;
    for(int cnt=0; cnt<n; cnt++)
        for(int i=0,j=cnt; i<=cnt; i++, j--)
            for(int k=0; k<=cnt; k++) {
                mins(dp[k + (dp[k][i][j][0]+X[i+1]-X[i]<=T[i+1])][i+1][j][0], 
                dp[k][i][j][0]+X[i+1]-X[i]);

                mins(dp[k + (dp[k][i][j][1]+X[i+1]+L-X[n+1-j]<=T[i+1])][i+1][j][0],
                dp[k][i][j][1]+X[i+1]+L-X[n+1-j]);

                mins(dp[k + (dp[k][i][j][0]+X[i]+L-X[n-j]<=T[n-j])][i][j+1][1],
                dp[k][i][j][0]+X[i]+L-X[n-j]);

                mins(dp[k + (dp[k][i][j][1]+X[n+1-j]-X[n-j]<=T[n-j])][i][j+1][1],
                dp[k][i][j][1]+X[n+1-j]-X[n-j]);
            }
    for(int k=n; k>=0; k--)
        for(int cnt=k; cnt<=n; cnt++)
            for(int i=0,j=cnt; i<=cnt; i++, j--)
                for(int t : {0, 1})
                    if(dp[k][i][j][t]<inf) {
                        cout << k << '\n';
                        return 0;
                    }
    return 0;
}

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