Submission #752160

#	Time	Username	Problem	Language	Result	Execution time	Memory
752160		Kihihihi	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	153 ms	135268 KiB

ho_t3

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e18, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

const long long N = 205;

long long n, l;
vector<long long> x, t;

long long dp[N][N][N][2];

void solve()
{
    for (long long left = 0; left < N; left++)
    {
        for (long long right = 0; right < N; right++)
        {
            for (long long hv = 0; hv < N; hv++)
            {
                for (long long lr = 0; lr < 2; lr++)
                {
                    dp[left][right][hv][lr] = INF;
                }
            }
        }
    }

    cin >> n >> l;
    x.resize(n + 2);
    x[0] = 0;
    for (long long i = 1; i < n + 1; i++)
    {
        cin >> x[i];
    }
    x[n + 1] = l;
    t.resize(n + 2);
    t[0] = INF;
    for (long long i = 1; i < n + 1; i++)
    {
        cin >> t[i];
    }
    t[n + 1] = INF;
    n += 2;

    dp[1][1][2][0] = 0;
    for (long long sum = 2; sum < n; sum++)
    {
        for (long long left = 1; left < n + 1; left++)
        {
            long long right = sum - left;
            long long lidx = left - 1, ridx = n - right;
            if (right <= 0)
            {
                break;
            }

            for (long long hv = 2; hv < left + right + 1; hv++)
            {
                long long tol = x[lidx + 1] - x[lidx];
                long long add = (dp[left][right][hv][0] + tol <= t[lidx + 1]);
                dp[left + 1][right][hv + add][0] = min(dp[left + 1][right][hv + add][0], dp[left][right][hv][0] + tol);

                long long tor = l - (x[ridx - 1] - x[lidx]);
                add = (dp[left][right][hv][0] + tor <= t[ridx - 1]);
                dp[left][right + 1][hv + add][1] = min(dp[left][right + 1][hv + add][1], dp[left][right][hv][0] + tor);

                tor = x[ridx] - x[ridx - 1];
                add = (dp[left][right][hv][1] + tor <= t[ridx - 1]);
                dp[left][right + 1][hv + add][1] = min(dp[left][right + 1][hv + add][1], dp[left][right][hv][1] + tor);

                tol = l - (x[ridx] - x[lidx + 1]);
                add = (dp[left][right][hv][1] + tol <= t[lidx + 1]);
                dp[left + 1][right][hv + add][0] = min(dp[left + 1][right][hv + add][0], dp[left][right][hv][1] + tol);
            }
        }
    }

    long long ans = 0;
    for (long long left = 0; left < n + 1; left++)
    {
        for (long long right = 0; right < n + 1; right++)
        {
            for (long long hv = 0; hv < n + 1; hv++)
            {
                for (long long lr = 0; lr < 2; lr++)
                {
                    if (dp[left][right][hv][lr] != INF)
                    {
                        ans = max(ans, hv);
                    }
                }
            }
        }
    }
    ans -= 2;
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

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