제출 #1310063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310063		syanvu	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	124 ms	129480 KiB

ho_t3

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 1, inf = 1e9, mod = 998244353;

void solve(){
    int n, l;
    cin >> n >> l;
    int x[n + 2] = {}, t[n + 2], y[n + 2] = {};
    y[n + 1] = l;
    x[n + 1] = l;
    for(int i = 1; i <= n; i++){
        cin >> x[i];
        y[n - i + 1] = (l - x[i]);
    }
    for(int i = 1; i <= n; i++){
        cin >> t[i];
    }
    int dp[n + 2][n + 2][n + 2][2] = {};
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                for(int d = 0; d < 2; d++) dp[i][j][k][d] = inf;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if((i == 0 && j == 0) || i >= n - j + 1) continue;
            for(int k = 0; k <= n; k++){
                if(k > i + j) break;
                if(i > 0) dp[i][j][k][0] = min({dp[i][j][k][0], dp[i - 1][j][k][0] + min(x[i] - x[i - 1], x[i - 1] + y[n - i + 1]), dp[i - 1][j][k][1] + min(x[n - j + 1] - x[i], y[j] + x[i])});
                if(j > 0) dp[i][j][k][1] = min({dp[i][j][k][1], dp[i][j - 1][k][1] + min(y[j] - y[j - 1], y[j - 1] + x[n - j + 1]), dp[i][j - 1][k][0] + min(x[n - j + 1] - x[i], x[i] + y[j])});
                dp[i][j][k][1] = min(dp[i][j][k][0] + min(x[n - j + 1] - x[i], x[i] + y[j]), dp[i][j][k][1]);
                dp[i][j][k][0] = min(dp[i][j][k][1] + min(x[n - j + 1] - x[i], y[j] + x[i]), dp[i][j][k][0]);
                if(k > 0){
                    int dist = inf;
                    if(j > 0){
                        dist = min(dp[i][j - 1][k - 1][1] + min(y[j] - y[j - 1], y[j - 1] + x[n - j + 1]), dp[i][j - 1][k - 1][0] + min(x[n - j + 1] - x[i], x[i] + y[j]));
                        if(dist <= t[n - j + 1]) dp[i][j][k][1] = min(dp[i][j][k][1], dist);
                    }
                    if(i > 0){
                        dist = min(dp[i - 1][j][k - 1][0] + min(x[i] - x[i - 1], x[i - 1] + y[n - i + 1]), dp[i - 1][j][k - 1][1] + min(x[n - j + 1] - x[i], y[j] + x[i]));
                        if(dist <= t[i]) dp[i][j][k][0] = min(dp[i][j][k][0], dist);
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 1; k <= n; k++){
                if(dp[i][j][k][0] < inf || dp[i][j][k][1] < inf){ 
                    ans = max(ans, k);
                }
            }
        }
    }
    cout << ans;
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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