Submission #1322228

#TimeUsernameProblemLanguageResultExecution timeMemory
1322228pobeCollecting Stamps 3 (JOI20_ho_t3)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
void solve() {
    int n, l;
    cin >> n >> l;
    vector <int> x(n), t(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    int ans = 0;
    int inf = 2e18;
    vector <vector <vector <int>>> dp(2, vector <vector <int>> (n + 1, vector <int> (n + 1, 2e18)));
    auto last = dp;
    last[0][0][0] = 0;
    int st = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int f = 0; f + j < n; ++f) {
                if (last[0][j][f] != inf) {
                    if (j == 0) {
                        st = 0;
                    } else {
                        st = x[j - 1];
                    }
                    if (x[j] - st + last[0][j][f] <= t[j]) {
//                        cout << i << " " << j << " " << f << endl;
                        dp[0][j + 1][f] = min(dp[0][j + 1][f], x[j] - st + last[0][j][f]);
                    }
                    int ind = n - 1 - f;
                    if (l - x[ind] + st + last[0][j][f] <= t[ind]) {
                        dp[1][j][f + 1] = min(dp[1][j][f + 1], l - x[ind] + st + last[0][j][f]);
                    }
                }
                if (last[1][j][f] != inf) {
                    if (f == 0) {
                        st = l;
                    } else {
                        st = x[n - f];
                    }
                    if (last[1][j][f] + st - x[n - f - 1] <= t[n - f - 1]) {
//                        cout << i << " " << " " << j << " " << f << endl;
                        dp[1][j][f + 1] = min(dp[1][j][f + 1], last[1][j][f] + st - x[n - f - 1]);
                    }
                    if (last[1][j][f] + l - st + x[j] <= t[j]) {
//                        cout << i << " " << " " << j << " " << f << endl;
                        dp[0][j + 1][f] = min(dp[0][j + 1][f], last[1][j][f] + l - st + x[j]);
                    }
                }
            }
        }
        for (int j = 0; j <= n; ++j) {
            for (int f = 0; f + j < n; ++f) {
                if (f == 0) {
                    st = l;
                } else {
                    st = x[n - f];
                }
                dp[0][j + 1][f] = min(dp[0][j + 1][f], dp[1][j][f] + l - st + x[j]);
                dp[1][j][f + 1] = min(dp[1][j][f + 1], dp[1][j][f] + st - x[n - f - 1]);
                if (j == 0) {
                    st = 0;
                } else {
                    st = x[j - 1];
                }
                dp[1][j][f + 1] = min(dp[1][j][f + 1], l - x[n - f - 1] + st + dp[0][j][f]);
                dp[0][j + 1][f] = min(dp[0][j + 1][f], x[j] - st + dp[0][j][f]);
            }
        }
        bool flag = false;
        for (int j = 0; j <= n; ++j) {
            for (int f = 0; f + j <= n; ++f) {
//                cout << "{" << dp[0][j][f] << " " << dp[1][j][f] << "} ";
                if (dp[0][j][f] < inf || dp[1][j][f] < inf) {
                    flag = true;
                }
                last[0][j][f] = inf;
                last[1][j][f] = inf;
            }
//            cout << '\n';
        }
        swap(last, dp);
        if (flag) {
            ans = i + 1;
        } else {
            break;
        }
    }
    cout << ans << '\n';
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}
/*
4 19
3 7 12 14
2 0 5 4
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...