Submission #586704

#	Time	Username	Problem	Language	Result	Execution time	Memory
586704		TheEvilBird	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	143 ms	71300 KiB

ho_t3

#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

void solve() {
    int n, L;
    cin >> n >> L;
    vector<ll> x(n + 1, 0), t(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
    }
    int ans = 0;
    vector<vector<vector<vector<int>>>> dp(n + 3,
                                           vector<vector<vector<int>>> (n + 3,
                                                                        vector<vector<int>> (2,
                                                                                             vector<int> (n + 3, INF))));

    auto get_time = [&](int i, int j) {
        i %= (n + 1);
        j %= (n + 1);
        ll dist = abs(x[i] - x[j]);
        return min(dist, L - dist);
    };

    dp[0][0][0][0] = dp[0][0][1][0] = 0;
    for (int len = 0; len <= n; ++len) {
        for (int pref = 0; pref <= len; ++pref) {
            int suf = len - pref;
            for (int k = 0; k <= n; ++k) {
                if (k == 1 && (dp[pref][suf][0][k] != INF || dp[pref][suf][1][k] != INF)) {
                    int kek = 0;
                }
                if (dp[pref][suf][0][k] != INF) {
                    int a = pref;
                    int go1 = a + 1, go2 = n + 1 - suf - 1;
                    if (1 <= go1 && go1 <= n && go1 != a) {
                        ll time = get_time(a, go1);
                        if (time + dp[pref][suf][0][k] <= t[go1] &&
                            time + dp[pref][suf][0][k] < dp[pref + 1][suf][0][k + 1]) {
                            dp[pref + 1][suf][0][k + 1] = time + dp[pref][suf][0][k];
                        } else if (time + dp[pref][suf][0][k] < dp[pref + 1][suf][0][k]) {
                            dp[pref + 1][suf][0][k] = time + dp[pref][suf][0][k];
                        }
                    }
                    if (1 <= go2 && go2 <= n && go2 != a) {
                        ll time = get_time(a, go2);
                        if (time + dp[pref][suf][0][k] <= t[go2] &&
                            time + dp[pref][suf][0][k] < dp[pref][suf + 1][1][k + 1]) {
                            dp[pref][suf + 1][1][k + 1] = time + dp[pref][suf][0][k];
                        } else if (time + dp[pref][suf][0][k] < dp[pref][suf + 1][1][k]) {
                            dp[pref][suf + 1][1][k] = time + dp[pref][suf][0][k];
                        }
                    }
                }
                if (dp[pref][suf][1][k] != INF) {
                    int a = (n + 1 - suf) % (n + 1);
                    int go1 = (a == 0 ? n : a - 1), go2 = pref + 1;
                    if (1 <= go1 && go1 <= n && go1 != a) {
                        ll time = get_time(a, go1);
                        if (time + dp[pref][suf][1][k] <= t[go1] &&
                            time + dp[pref][suf][1][k] < dp[pref][suf + 1][1][k + 1]) {
                            dp[pref][suf + 1][1][k + 1] = time + dp[pref][suf][1][k];
                        } else if (time + dp[pref][suf][1][k] < dp[pref][suf + 1][1][k]) {
                            dp[pref][suf + 1][1][k] = time + dp[pref][suf][1][k];
                        }
                    }
                    if (1 <= go2 && go2 <= n && go2 != a) {
                        ll time = get_time(a, go2);
                        if (time + dp[pref][suf][1][k] <= t[go2] &&
                            time + dp[pref][suf][1][k] < dp[pref + 1][suf][0][k + 1]) {
                            dp[pref + 1][suf][0][k + 1] = time + dp[pref][suf][1][k];
                        } else if (time + dp[pref][suf][1][k] < dp[pref + 1][suf][0][k]) {
                            dp[pref + 1][suf][0][k] = time + dp[pref][suf][1][k];
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= 1; ++k) {
                for (int cnt = 0; cnt <= n; ++cnt) {
                    if (i + j <= n && dp[i][j][k][cnt] != INF) {
//                        cerr << i << ' ' << j << ' ' << k << ' ' << cnt << endl;
                        ans = max(ans, cnt);
                    }
                }
            }
        }
    }
    cout << ans << en;
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'void solve()':
ho_t3.cpp:70:25: warning: unused variable 'kek' [-Wunused-variable]
   70 |                     int kek = 0;
      |                         ^~~

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