Submission #779305

#	Time	Username	Problem	Language	Result	Execution time	Memory
779305		1bin	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	78 ms	135372 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const ll inf = 1e18;
ll n, L, X[205], T[205], dp[205][205][205][2], d1, d2;
int ans;

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> L;
    for(int i = 1; i <= n; i++) cin >> X[i];
    for(int i = 1; i <= n; i++) cin >> T[i];
    X[n + 1] = L;
    fill(&dp[0][0][0][0], &dp[204][204][204][2], inf);
    dp[0][n + 1][0][0] = 0;
    for(int l = 0; l <= n; l++)
        for(int r = n + 1; r > l; r--)
            for(int j = 0; j <= n; j++){
                if(l){
                    d1 = X[l] - X[l - 1];
                    d2 = L - X[r] + X[l];
                    dp[l][r][j][0] = min(dp[l - 1][r][j][0] + d1, dp[l - 1][r][j][1] + d2);
                    if(j){
                        if(dp[l - 1][r][j - 1][0] + d1 <= T[l]) dp[l][r][j][0] = min(dp[l][r][j][0], dp[l - 1][r][j - 1][0] + d1);
                        if(dp[l - 1][r][j - 1][1] + d2 <= T[l]) dp[l][r][j][0] = min(dp[l][r][j][0], dp[l - 1][r][j - 1][1] + d2);
                    }
                    if(dp[l][r][j][0] < inf) ans = max(ans, j);
                }
                
                if(r < n + 1){
                    d1 = X[r + 1] - X[r];
                    d2 = L - X[r] + X[l];
                    dp[l][r][j][1] = min(dp[l][r + 1][j][1] + d1, dp[l][r + 1][j][0] + d2);
                    if(j){
                        if(dp[l][r + 1][j - 1][0] + d2 <= T[r]) dp[l][r][j][1] = min(dp[l][r][j][1], dp[l][r + 1][j - 1][0] + d2);
                        if(dp[l][r + 1][j - 1][1] + d1 <= T[r]) dp[l][r][j][1] = min(dp[l][r][j][1], dp[l][r + 1][j - 1][1] + d1);
                    }
                    if(dp[l][r][j][1] < inf) ans = max(ans, j);
                }
            }
    cout << ans;
    return 0;
}

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