Submission #1282200

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282200		shirokito	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	127 ms	176392 KiB

ho_t3

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

using ll = long long;

template <class T> bool maximize(T &x, T y) {
    return (x < y) && (x = y, 1);
}
template <class T> bool minimize(T &x, T y) {
    return (x > y) && (x = y, 1);
}

const int N = 200 + 24;
const ll INF = 1e18;

int n; ll L;
ll x[N], t[N];
ll dp[N][N][2][N];

ll dist(ll px, ll py) {
    return min(L - abs(px - py), abs(px - py));
}

void solve() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    x[0] = L, t[0] = INF; 
    x[n + 1] = L, t[n + 1] = INF; 

    memset(dp, 0x3f, sizeof(dp));

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

    for (int i = 0; i <= n + 1; i++) {
        for (int j = n + 1; j >= i + 2; j--) {
            for (int p = 0; p <= 1; p++) {
                for (int g = 0; g <= i + (n - j + 1); g++) {
                    ll new_t, new_g;

                    new_t = dp[i][j][p][g] + dist(x[(p == 0 ? i : j)], x[j - 1]);
                    new_g = g + (new_t <= t[j - 1]);
                    minimize(dp[i][j - 1][p][g], new_t);
                    minimize(dp[i][j - 1][1][new_g], new_t);

                    new_t = dp[i][j][p][g] + dist(x[(p == 0 ? i : j)], x[i + 1]);
                    new_g = g + (new_t <= t[i + 1]);
                    minimize(dp[i + 1][j][p][g], new_t);
                    minimize(dp[i + 1][j][0][new_g], new_t);
                }
            }
        }
    }

    for (int g = n; g >= 0; g--) {
        for (int i = 0; i <= n + 1; i++) {
            for (int j = n + 1; j >= i + 1; j--) {
                for (int p = 0; p <= 1; p++) {
                    if (dp[i][j][p][g] < INF) {
                        cout << g << '\n';
                        return;
                    }
                }
            }   
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    #define task "joi20_ho_t3"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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