Submission #1173153

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

ho_t3

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

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 dist = [&](int x, int y) {
        int ans = abs(x - y);
        ans = min(ans, L - max(x, y) + min(x, y));
        return ans;
    };

    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++) {
                int nk = k + (t[i+1] >= dp[i][j][k][0] + dist(p[i], p[i+1]));
                dp[i+1][j][nk][0] = min(dp[i+1][j][nk][0], dp[i][j][k][0] + dist(p[i], p[i+1]));

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

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

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

    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