Submission #1173154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173154		VMaksimoski008	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	60 ms	67144 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[205][205][205][2];

signed main() {
    int n, L, ans = 0; cin >> n >> L;
    vector<int> p(n+2); p[0] = p[n+1] = L;
    vector<int> t(n+2); t[0] = t[n+1] = -1;

    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++) cin >> t[i];

    auto D = [&](int x, int y) {
        return min( abs(x - y), L - abs(x - y) );
    };

    for(int i=0; i<=n+1; i++)
        for(int j=i; j<=n+1; j++)
            for(int k=0; k<=n; k++) dp[i][j][k][0] = dp[i][j][k][1] = 1e18;

    dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0;

    for(int i=0; i<=n+1; i++) {
        for(int j=n+1; j>=i+2; j--) {
            for(int k=0; k<n; k++) {
                ll d = dp[i][j][k][0] + D(p[i], p[i+1]);
                int nk = k + (t[i+1] >= d);
                dp[i+1][j][nk][0] = min(dp[i+1][j][nk][0], d);

                d = dp[i][j][k][1] + D(p[j], p[j-1]);
                nk = k + (t[j-1] >= d);
                dp[i][j-1][nk][1] = min(dp[i][j-1][nk][1], d);

                d = dp[i][j][k][1] + D(p[j], p[i+1]);
                nk = k + (t[i+1] >= d);
                dp[i+1][j][nk][0] = min(dp[i+1][j][nk][0], d);

                d = dp[i][j][k][0] + D(p[i], p[j-1]);
                nk = k + (t[j-1] >= d);
                dp[i][j-1][nk][1] = min(dp[i][j-1][nk][1], d);
            }
        }
    }

    for(int i=0; i<=n+1; i++)
        for(int j=i; j<=n+1; j++)
            for(int k=0; k<=n; k++)
                for(int l : { 0, 1 })
                if(dp[i][j][k][l] != 1e18)
                    ans = max(ans, k);
    cout << ans << '\n';
}

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