제출 #568160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568160		Ronin13	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	65 ms	127564 KiB

ho_t3

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int inf = 1e9 + 1;
const ll linf = 1e18 + 1;

ll dp[201][201][201][2];

int main(){
    ll n, l;
    cin >> n >> l;
    ll a[n + 2];
    ll t[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> t[i];
    }
    for(int i = 0; i <= 200; i++){
        for(int j = 0; j <= 200; j++){
            for(int k = 0; k <= 200; k++) dp[i][j][k][0] = dp[i][j][k][1] = linf;
        }
    }
    dp[0][0][0][0] = 0;
    a[0] = 0;
    a[n + 1] = l;
    // 0 marcxniv 1 marjvniv
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(i + j > n) continue;
            for(int x = 0; x < n; x++){
                ll nt = dp[i][j][x][0] + l - a[n - i + 1] + a[j + 1];
                nt = min(nt, dp[i][j][x][1] + a[j + 1] - a[j]);
                if(nt <= t[j + 1]) dp[i][j + 1][x + 1][1] = min(dp[i][j + 1][x + 1][1], nt);
                else dp[i][j + 1][x][1] = min(dp[i][j + 1][x][1], nt);
                nt = dp[i][j][x][0] + a[n - i + 1] - a[n - i];
                nt = min(nt, dp[i][j][x][1] + l - a[n - i] + a[j]);
                if(nt <= t[n - i]) dp[i + 1][j][x + 1][0] = min(dp[i + 1][j][x + 1][0], nt);
                else dp[i + 1][j][x][0] = min(dp[i + 1][j][x][0], nt);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int x = 1; x <= n; x++) {
            if(dp[i][n - i][x][0] != linf) ans = max(x, ans);
            if(dp[i][n - i][x][1] != linf) ans = max(x, ans);
        }
    }
    cout << ans;
    return 0;
}

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