Submission #967386

#	Time	Username	Problem	Language	Result	Execution time	Memory
967386		12345678	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	96 ms	130156 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=205;

ll n, d, a[nx], t[nx], dp[nx][nx][nx][2], res;

ll dist(ll a, ll b)
{
    if (a>b) swap(a, b);
    return min(b-a, a+d-b);
}

ll nxt(ll x)
{
    if (x+1>n) return x+1-n;
    return x+1;
}

ll prv(ll x)
{
    if (x-1>0) return x-1;
    return x-1+n;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>d;
    for (int i=1; i<=n; i++) cin>>a[i];
    for (int i=1; i<=n; i++) cin>>t[i];
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) dp[i][j][k][0]=dp[i][j][k][1]=1e18;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j][0][0]=dist(0, a[i]), dp[i][j][0][1]=dist(0, a[j]);
    for (int i=1; i<=n; i++) if (dist(0, a[i])<=t[i]) dp[i][i][1][0]=dp[i][i][1][1]=dist(0, a[i]);
    for (int i=1; i<n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            ll l=j, r=j+i;
            if (r>n) r-=n;
            for (int k=1; k<=i+1; k++)
            {
                dp[l][r][k][0]=min({dp[l][r][k][0], dp[nxt(l)][r][k][0]+dist(a[l], a[nxt(l)]), dp[nxt(l)][r][k][1]+dist(a[l], a[r])});
                if (dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][0]+dist(a[nxt(l)], a[l]));
                if (dp[nxt(l)][r][k-1][1]+dist(a[l], a[r])<=t[l]) dp[l][r][k][0]=min(dp[l][r][k][0], dp[nxt(l)][r][k-1][1]+dist(a[l], a[r]));
                dp[l][r][k][1]=min({dp[l][r][k][1], dp[l][prv(r)][k][0]+dist(a[l], a[r]), dp[l][prv(r)][k][1]+dist(a[prv(r)], a[r])});
                if (dp[l][prv(r)][k-1][0]+dist(a[l], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][0]+dist(a[l], a[r]));
                if (dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r])<=t[r]) dp[l][r][k][1]=min(dp[l][r][k][1], dp[l][prv(r)][k-1][1]+dist(a[prv(r)], a[r]));
                //cout<<"debug "<<l<<' '<<r<<' '<<k<<' '<<dp[l][r][k][0]<<' '<<dp[l][r][k][1]<<'\n';
            }
        }
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int k=1; k<=n; k++) for (int t=0; t<2; t++) if (dp[i][j][k][t]<1e18) res=max(res, (ll)k);
    cout<<res;
}

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