Submission #958147

#	Time	Username	Problem	Language	Result	Execution time	Memory
958147		peterandvoi	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	69 ms	135368 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long

const int N = 205;

int n, l;
int x[N], t[N];
int dp[N][N][N][2];

template<class A, class B>
bool mini(A &a, const B &b) {
    return a > b ? (a = b), true : false;
}

int dis(int a, int b) {
    if (x[a] > x[b]) {
        swap(a, b);
    }
    return min(x[b] - x[a], x[a] + l - x[b]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> l;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    const int INF = (int) 1e18;
    dp[0][0][0][0] = 0;
    int res = 0;
    for (int len = 0; len < n; ++len) {
        for (int L = 0; L <= len; ++L) {
            int R = len - L;
            for (int cnt = 0; cnt <= len; ++cnt) {
                for (int j = 0; j < 2; ++j) {
                    if (dp[L][R][cnt][j] < INF) {
                        res = max(res, cnt);
                        int T = dp[L][R][cnt][j];
                        int cur = j == 0 ? n + 1 - L : R;
                        if (T + dis(cur, n - L) <= t[n - L]) {
                            res = max(res, cnt + 1);
                            mini(dp[L + 1][R][cnt + 1][0], T + dis(cur, n - L));
                        } else {
                            mini(dp[L + 1][R][cnt][0], T + dis(cur, n - L));
                        }
                        if (T + dis(cur, R + 1) <= t[R + 1]) {
                            res = max(res, cnt + 1);
                            mini(dp[L][R + 1][cnt + 1][1], T + dis(cur, R + 1));
                        } else {
                            mini(dp[L][R + 1][cnt][1], T + dis(cur, R + 1));
                        }
                    }
                }
            }
        }
    }
    cout << res;
}

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