Submission #442058

#	Time	Username	Problem	Language	Result	Execution time	Memory
442058		idontreallyknow	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	127 ms	135384 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define fi first
#define se second
#define SZ(x) ((int)((x).size()))
#define debug(x) cerr << #x << " = " << x << '\n'
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}
const int mx = 205;
ll n, l, dp[mx][mx][mx][2], inf = (ll)1e17+5;
pii p[mx];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    for (int q = 1; q <= n; q++) cin >> p[q].fi;
    for (int q = 1; q <= n; q++) cin >> p[q].se;
    p[n+1] = {l,-1};
    for (int q = 0; q < mx; q++) 
        for (int w = 0; w < mx; w++) 
            for (int e = 0; e < mx; e++) 
                dp[q][w][e][0] = dp[q][w][e][1] = inf;
    for (int q = 0; q <= n; q++) {
        for (int w = n+1; w > q; w--) {
            if (q == 0 && w == n+1) {
                dp[q][w][0][0] = dp[q][w][0][1] = 0;
                continue;
            }
            for (int e = 0; e < mx; e++) {
                if (q == 0) {
                    chkmin(dp[q][w][e][1], dp[q][w+1][e][1]+p[w+1].fi-p[w].fi);
                    if (e > 0 && dp[q][w+1][e-1][1]+p[w+1].fi-p[w].fi <= p[w].se) {
                        chkmin(dp[q][w][e][1], dp[q][w+1][e-1][1]+p[w+1].fi-p[w].fi);
                    }
                    chkmin(dp[q][w][e][0], dp[q][w][e][1]+l-p[w].fi);
                } else if (w == n+1) {
                    chkmin(dp[q][w][e][0], dp[q-1][w][e][0]+p[q].fi-p[q-1].fi);
                    if (e > 0 && dp[q-1][w][e-1][0]+p[q].fi-p[q-1].fi <= p[q].se) {
                        chkmin(dp[q][w][e][0], dp[q-1][w][e-1][0]+p[q].fi-p[q-1].fi);
                    }
                    chkmin(dp[q][w][e][1], dp[q][w][e][0]+p[q].fi);
                } else {
                    chkmin(dp[q][w][e][0], dp[q-1][w][e][0]+p[q].fi-p[q-1].fi);
                    chkmin(dp[q][w][e][0], dp[q-1][w][e][1]+l-p[w].fi+p[q].fi);
                    chkmin(dp[q][w][e][1], dp[q][w+1][e][1]+p[w+1].fi-p[w].fi);
                    chkmin(dp[q][w][e][1], dp[q][w+1][e][0]+p[q].fi+l-p[w].fi);
                    if (e > 0) {
                        if (dp[q-1][w][e-1][0]+p[q].fi-p[q-1].fi <= p[q].se) {
                            chkmin(dp[q][w][e][0], dp[q-1][w][e-1][0]+p[q].fi-p[q-1].fi);
                        }
                        if (dp[q-1][w][e-1][1]+l-p[w].fi+p[q].fi <= p[q].se) {
                            chkmin(dp[q][w][e][0], dp[q-1][w][e-1][1]+l-p[w].fi+p[q].fi);
                        }
                        if (dp[q][w+1][e-1][1]+p[w+1].fi-p[w].fi <= p[w].se) {
                            chkmin(dp[q][w][e][1], dp[q][w+1][e-1][1]+p[w+1].fi-p[w].fi);
                        }
                        if (dp[q][w+1][e-1][0]+p[q].fi+l-p[w].fi <= p[w].se) {
                            chkmin(dp[q][w][e][1], dp[q][w+1][e-1][0]+p[q].fi+l-p[w].fi);
                        }
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int q = 0; q < mx; q++) 
        for (int w = 0; w < mx; w++)
            for (int e = 0; e < mx; e++)
                for (int r = 0; r < 2; r++)
                    if (dp[q][w][e][r] != inf) ans = max(ans, e);
    cout << ans << '\n';
    return 0;
}

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