Submission #1254173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254173		tvgk	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	324 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 2e2 + 7, inf = 1e9 + 7;

int n, l, a[mxN];
ii t[mxN], dp[mxN][mxN][3];

bool Between(int u, int id, int v)
{
    if (u <= v)
        return (u <= id && id <= v);
    else
        return !(v < id && id < u);
}

int dis(int u, int v)
{
    return (a[v] + l - a[u]) % l;
}

ii Plus(ii u, ii v)
{
    u.fi += v.fi;
    u.se -= v.se;
    return u;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i].fi;
        t[i].se = i;
    }
    sort(t + 1, t + n + 1);

    /*
    dp[i][j][0/1] la time nho nhat
    tai vi tri i
    0 la trai
    1 la phai
    j la dau con lai
    */

    // Reset dp
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
            for (int dir = 0; dir <= 1; dir++)
                dp[i][j][dir] = {inf, 0};
    }

    dp[0][0][0].fi = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            for (int u = 0; u <= n; u++)
            {
                //dir = 0
                if (!Between(u, t[i].se, t[j].se))
                {
                    // nw dir = 0
                    dp[i][u][0] = min(dp[i][u][0], Plus(dp[j][u][0], {dis(t[j].se, t[i].se), 1}));

                    // nw dir = 1
                    dp[i][t[j].se][1] = min(dp[i][t[j].se][1], Plus(dp[j][u][0], {dis(t[i].se, t[j].se), 1}));
                }
                else
                    dp[j][u][0].se--;

                // dir = 1
                if (!Between(t[j].se, t[i].se, u))
                {
                    // nw dir = 1
                    dp[i][u][1] = min(dp[i][u][1], Plus(dp[j][u][1], {dis(t[i].se, t[j].se), 1}));

                    // nw dir = 0
                    dp[i][t[j].se][0] = min(dp[i][t[j].se][0], Plus(dp[j][u][1], {dis(t[j].se, t[i].se), 1}));
                }
                else
                    dp[j][u][1].se--;
            }
        }

        for (int j = 0; j <= n; j++)
        {
            for (int dir = 0; dir <= 1; dir++)
            {
                if (dp[i][j][dir].fi > t[i].fi)
                    dp[i][j][dir] = {inf, 0};
            }
        }
    }

    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
            for (int dir = 0; dir <= 1; dir++)
            {
                if (dp[i][j][dir].fi != inf)
                    ans = max(-dp[i][j][dir].se, ans);
            }
    }
    cout << ans;
}

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