Submission #201475

#	Time	Username	Problem	Language	Result	Execution time	Memory
201475		Alexa2001	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	101 ms	66680 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 99;
const int Nmax = 205;

int dp[Nmax][Nmax][Nmax][2];
int n, L, d[Nmax], t[Nmax];
int ans = 0;

void min_to(int &x, int y)
{
    if(x > y) x = y;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> L;
    int i, j, k;
    for(i=1; i<=n; ++i) cin >> d[i];
    for(i=1; i<=n; ++i) cin >> t[i];

    d[0] = 0; d[n+1] = L;

    for(i=0; i<=n+1; ++i)
        for(j=0; j<=n+1;++j)
            for(k=0; k<=n+1; ++k)
                dp[i][j][k][0] = dp[i][j][k][1] = inf;

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

    for(i=n+1; i; --i)
        for(j=0; j<i; ++j)
            for(k=0; k<=n; ++k)
            {
                int tmp;
           //     if(i == 4) exit(0);
                
                if(dp[i][j][k][0] < inf)
                {
                    /// 0, j -> j+1
                    if(j + 1 < i)
                    {
                        tmp = dp[i][j][k][0] + (d[j+1] - d[j]);
                        min_to(dp[i][j+1][k + (tmp <= t[j+1])][0], tmp);
                    }

                    /// 0, i->i-1
                    if(j < i-1)
                    {
                        tmp = dp[i][j][k][0] + d[j] + (L - d[i-1]);
                        min_to(dp[i-1][j][k + (tmp <= t[i-1])][1], tmp);
                    }

                    ans = max(ans, k);
            //        cerr << i << ' ' << j << ' ' << k << ' ' << 0 << ' ' << dp[i][j][k][0] << '\n';
                } 


                if(dp[i][j][k][1] < inf)
                {
                    /// 1, i->i-1
                    if(j < i-1)
                    {
                        tmp = dp[i][j][k][1] + (d[i] - d[i-1]);
                        min_to(dp[i-1][j][k + (tmp <= t[i-1])][1], tmp);
                    }

                    /// 1, j->j+1
                    if(j + 1 < i)
                    {
                        tmp = dp[i][j][k][1] + (L - d[i]) + d[j+1];
                        min_to(dp[i][j+1][k + (tmp <= t[j+1])][0], tmp);
                    }
                    
                    ans = max(ans, k);
              //      cerr << i << ' ' << j << ' ' << k << ' ' << 1 << ' ' << dp[i][j][k][1] << '\n';
                }
            }

    cout << ans << '\n';

    return 0;
}

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