Submission #1208570

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

ho_t3

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define int long long

const int MAXN = 202;
int per;
int dp[MAXN][MAXN][MAXN][2];

int give_best(int l, int r)
{
    return std::min(std::abs(r - l), per - std::abs(r - l));
}

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    std::cin >> n;
    std::cin >> per;

    std::vector<int> x;
    x.push_back(0);
    std::vector<int> t;
    t.push_back(1e9);
    for (int i = 0; i < n; i++)
    {
        int help;
        std::cin >> help;
        x.push_back(help);
    }
    for (int i = 0; i < n; i++)
    {
        int help;
        std::cin >> help;
        t.push_back(help);
    }

    if (n == 1)
    {
        if (t[1] >= std::min(per - x[1], x[1]))
        {
            std::cout << 1;
        }
        else
        {
            std::cout << 0;
        }
        return 0;
    }

    for (int l = 0; l <= n; l++)
    {
        for (int r = 0; r <= n; r++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[l][r][j][0] = 1e13;
                dp[l][r][j][1] = 1e13;
            }
        }
    }

    int max = 0;

    dp[1][n][0][0] = 0;
    dp[1][n][0][1] = 0;

    for (int len = n - 1; len >= 0; len--)
    {
        for (int l = 1; l <= n - len; l++)
        {
            int r = l + len - 1;
            for (int j = 0; j <= (n - len); j++)
            {

                if (j > 0 && l > 1)
                {
                    if (dp[l - 1][r][j - 1][0] + give_best(x[l - 1], x[l - 2]) <= t[l - 1])
                    {
                        dp[l][r][j][0] = std::min(dp[l][r][j][0],
                                                  dp[l - 1][r][j - 1][0] +
                                                      give_best(x[l - 1], x[l - 2]));
                    }
                    else
                    {
                        dp[l][r][j][0] = std::min(dp[l][r][j][0],
                                                  dp[l - 1][r][j][0] + give_best(x[l - 1], x[l - 2]));
                    }
                }
                else if (l > 1)
                {
                    dp[l][r][j][0] = std::min(dp[l][r][j][0],
                                              dp[l - 1][r][j][0] + give_best(x[l - 1], x[l - 2]));
                }

                if (j > 0 && r < n)
                {
                    // std::cout << t[r + 1] << ' ' << give_best(x[(r + 2) % (n + 1)], x[r + 1]) << std::endl;
                    if (dp[l][r + 1][j - 1][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1]) <= t[r + 1])
                    {
                        dp[l][r][j][1] = std::min(dp[l][r][j][1],
                                                  dp[l][r + 1][j - 1][1] +
                                                      give_best(x[(r + 2) % (n + 1)], x[r + 1]));
                    }
                    else
                    {
                        dp[l][r][j][1] = std::min(dp[l][r][j][1],
                                                  dp[l][r + 1][j][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1]));
                    }
                }
                else if (r < n)
                {
                    dp[l][r][j][1] = std::min(dp[l][r][j][1],
                                              dp[l][r + 1][j][1] + give_best(x[(r + 2) % (n + 1)], x[r + 1]));
                }

                if (dp[l][r][j][0] < dp[l][r][j][1])
                {
                    int help = (r + 1) % (n + 1);
                    int help1 = l - 1;
                    dp[l][r][j][1] = std::min(dp[l][r][j][1],
                                              dp[l][r][j][0] + give_best(x[help], x[help1]));
                }
                else
                {
                    int help = (r + 1) % (n + 1);
                    int help1 = l - 1;
                    dp[l][r][j][0] = std::min(dp[l][r][j][0],
                                              dp[l][r][j][1] + give_best(x[help], x[help1]));
                }
                // std::cout << l << ' ' << r << ' ' << j << ' ' << dp[l][r][j][0] << ' ' << dp[l][r][j][1] << std::endl;
                if (dp[l][r][j][0] < 1e13 || dp[l][r][j][1] < 1e13)
                {
                    max = std::max(max, j);
                }
            }
        }
    }
    std::cout << max;
}

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