Submission #1315970

#TimeUsernameProblemLanguageResultExecution timeMemory
1315970kkkkkCollecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e2 + 11;
const int inf = 1e9 + 7;
int x[N], t[N], n, L;
int dp[N][N][2];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    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;

    vector < vector < vector < int > > > dp(n + 1, vector < vector < int > >(n + 1, vector < int >(2, inf)));
    dp[0][0][0] = dp[0][0][1] = 0;
    int ans = 0;
    for(int k = 1; k <= n; k++){
        vector < vector < vector < int > > > ndp(n + 1, vector < vector < int > >(n + 1, vector < int >(2, inf)));
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n - i; j++){
                if(i > 0){
                    int T = dp[i - 1][j][0] + x[n - i + 2] - x[n - i + 1];
                    if(T <= t[n - i + 1]) ndp[i][j][0] = min(ndp[i][j][0], T);
                    T = dp[i - 1][j][1] + x[j] + L - x[n - i + 1];
                    if(T <= t[n - i + 1]) ndp[i][j][0] = min(ndp[i][j][0], T);
                }
                if(j > 0){
                    int T = dp[i][j - 1][0] + L - x[n - i + 1] + x[j];
                    if(T <= t[j]) ndp[i][j][1] = min(ndp[i][j][1], T);
                    T = dp[i][j - 1][1] + x[j] - x[j - 1];
                    if(T <= t[j]) ndp[i][j][1] = min(ndp[i][j][1], T);
                }
                if(i > 0) ndp[i][j][0] = min(ndp[i][j][0], ndp[i - 1][j][0] + x[n - i + 2] - x[n - i + 1]);
                if(i > 0) ndp[i][j][0] = min(ndp[i][j][0], ndp[i - 1][j][1] + x[j] + L - x[n - i + 1]);
                if(j > 0) ndp[i][j][1] = min(ndp[i][j][1], ndp[i][j - 1][0] + x[j] + L - x[n - i + 1]);
                if(j > 0) ndp[i][j][1] = min(ndp[i][j][1], ndp[i][j - 1][1] + x[j] - x[j - 1]);
                if(ndp[i][j][1] != inf || ndp[i][j][0] != inf) ans = k;
            }
        }
        dp = ndp;
    }
    cout << ans;
}
// subete no mono no owari wa sugu ni yattekuru
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...