Submission #297809

#	Time	Username	Problem	Language	Result	Execution time	Memory
297809		balbit	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	73 ms	133368 KiB

ho_t3

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

void GG(){cout<<-1<<endl; exit(0);}

const int maxn = 204;

ll n,L;
ll X[maxn], T[maxn];
ll dp[maxn][maxn][2][maxn]; // (l,r) is not explored, ,stamps)

signed main(){
    IOS();
    memset(dp, 0x3f, sizeof dp);
    cin>>n>>L;
    for (ll i = 1 ;i<=n; ++i) cin>>X[i];
    X[n+1] = L;
    for (ll i = 1 ;i<=n; ++i) cin>>T[i];
    ++n;
    dp[0][n][0][0]=0;
    dp[0][n][1][0]=0;
    T[0] = -1;
    ll re = 0;
    for (ll df = n-1; df >= 1; --df) {
        for (ll i = 0; i+df <= n; ++i) {
            ll j = i+df;
            for (ll g = 0; g <= n; ++g) {
                if (i)
                    MN(dp[i][j][0][g], dp[i-1][j][0][g] + X[i] - X[i-1]);
                if (j!=n)
                    MN(dp[i][j][1][g], dp[i][j+1][1][g] + X[j+1] - X[j]);
                if (g) {
                    if (i && dp[i-1][j][0][g-1] + X[i] - X[i-1] <= T[i])
                        MN(dp[i][j][0][g], dp[i-1][j][0][g-1] + X[i] - X[i-1]);

                    if (j != n && dp[i][j+1][0][g-1] + X[j+1] - X[j] <= T[j])
                        MN(dp[i][j][1][g], dp[i][j+1][1][g-1] + X[j+1] - X[j]);
                }
                MN(dp[i][j][0][g], dp[i][j][1][g] + L - X[j] + X[i]);
                MN(dp[i][j][1][g], dp[i][j][0][g] + L - X[j] + X[i]);
                if (min(dp[i][j][0][g],dp[i][j][1][g]) < 10000000000ll) {
                    MX(re, g);
                    bug(dp[i][j][0][g], i,j,g);
                }
            }

        }
    }

    cout<<re<<endl;
}

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