Submission #255147

#	Time	Username	Problem	Language	Result	Execution time	Memory
255147		AM1648	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	136 ms	145528 KiB

ho_t3

/* be name khoda */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define forifrom(i, s, n) for (ll i = s; i < n; ++i)
#define fori(i, n) forifrom(i, 0, n)
#define forirto(i, n, e) for (ll i = (n) - 1; i >= e; --i)
#define forir(i, n) forirto(i, n, 0)

#define smin(a, b) a = min(a, b)

// ------------------------------------------------------------------

const ll INF = 4340410370284600380LL;
const ll maxn = 210;

ll N, L, X[maxn], T[maxn], dp[maxn][maxn][maxn][2];
// dp[k][l][r][2] -> minimum time to get k stamps

void update(ll k, ll l, ll r, ll b, ll a) {
    smin(dp[k][l][r][b], a);
    if (b == 0 && T[l] >= a || b == 1 && T[r] >= a) smin(dp[k + 1][l][r][b], a);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //ifstream cin("3.in");

    cin >> N >> L;
    fori (i, N) cin >> X[i + 1];
    fori (i, N) cin >> T[i + 1];
    X[N + 1] = L;

    memset(dp, 60, sizeof dp);
    ll ans = 0; 
    dp[0][0][N + 1][0] = dp[0][0][N + 1][1] = 0;
    fori (k, N + 1) {
        forirto (t, N + 2, 1) {
            fori (l, N - t + 2) {
                ll r = l + t;
                ll vl = dp[k][l][r][0], vr = dp[k][l][r][1];
                if (vl < INF) {
                    ans = k;
                    update(k, l + 1, r, 0, vl + X[l + 1] - X[l]);
                    update(k, l, r - 1, 1, vl + X[l] + L - X[r - 1]);
                }
                if (vr < INF) {
                    ans = k;
                    update(k, l, r - 1, 1, vr + X[r] - X[r - 1]);
                    update(k, l + 1, r, 0, vr + L - X[r] + X[l + 1]);
                }
            }
        }
    }
    cout << ans << '\n';

}

Compilation message (stderr)

ho_t3.cpp: In function 'void update(ll, ll, ll, ll, ll)':
ho_t3.cpp:24:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (b == 0 && T[l] >= a || b == 1 && T[r] >= a) smin(dp[k + 1][l][r][b], a);
         ~~~~~~~^~~~~~~~~~~~

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