Submission #575433

#	Time	Username	Problem	Language	Result	Execution time	Memory
575433		vasilykuzmin22	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	60 ms	72908 KiB

ho_t3

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;

//#define int long long

const int SIZE = 210;
const int INF = 1e9 + 9;
const long long INFL = 1e18 + 9;

int dp[SIZE][SIZE][SIZE][2];

signed main()
{
    for (int i = 0; i < SIZE; ++i)
    {
        for (int j = 0; j < SIZE; ++j)
        {
            for (int k = 0; k < SIZE; ++k)
            {
                dp[i][j][k][0] = INF;
                dp[i][j][k][1] = INF;
            }
        }
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    
    int n, l;
    cin >> n >> l;
    vector <int> x(n + 1);
    x[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i];
    }
    vector <int> t(n + 1);
    t[0] = -1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> t[i];
    }

    int gans = 0;
    dp[0][0][0][0] = 0;
    for (int ans = 0; ans <= n; ++ans)
    {
        for (int ll = 0; ll <= n; ++ll)
        {
            for (int rr = 0; rr <= n; ++rr)
            {
                if (dp[ans][ll][rr][0] != INF || dp[ans][ll][rr][1] != INF)
                    gans = max(ans, gans);

                if (ll + rr >= n)
                {
                    continue;
                }

                if (dp[ans][ll][rr][0] != INF)
                {
                    int tt = dp[ans][ll][rr][0] + x[ll + 1] - x[ll];
                    if (tt <= t[ll + 1])
                    {
                        dp[ans + 1][ll + 1][rr][0] = min(dp[ans + 1][ll + 1][rr][0], tt);
                    }
                    else 
                    {
                        dp[ans][ll + 1][rr][0] = min(dp[ans][ll + 1][rr][0], tt);
                    }

                    tt = dp[ans][ll][rr][0] + l - (x[n - rr] - x[ll]);
                    if (tt <= t[n - rr])
                    {
                        dp[ans + 1][ll][rr + 1][1] = min(dp[ans + 1][ll][rr + 1][1], tt);
                    }
                    else 
                    {
                        dp[ans][ll][rr + 1][1] = min(dp[ans][ll][rr + 1][1], tt);
                    }
                }

                if (dp[ans][ll][rr][1] != INF)
                {
                    int tt = dp[ans][ll][rr][1] + x[n - rr + 1] - x[n - rr];
                    if (tt <= t[n - rr])
                    {
                        dp[ans + 1][ll][rr + 1][1] = min(dp[ans + 1][ll][rr + 1][1], tt);
                    }
                    else 
                    {
                        dp[ans][ll][rr + 1][1] = min(dp[ans][ll][rr + 1][1], tt);
                    }

                    tt = dp[ans][ll][rr][1] + l - (x[n - rr + 1] - x[ll + 1]);
                    if (tt <= t[ll + 1])
                    {
                        dp[ans + 1][ll + 1][rr][0] = min(dp[ans + 1][ll + 1][rr][0], tt);
                    }
                    else 
                    {
                        dp[ans][ll + 1][rr][0] = min(dp[ans][ll + 1][rr][0], tt);
                    }
                }
            }
        }
    }

    // cerr << dp[5][0][5][1] << '\n';

    cout << gans;

    return 0;
}

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