Submission #342765

#	Time	Username	Problem	Language	Result	Execution time	Memory
342765		blue	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	291 ms	129404 KiB

ho_t3

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

long long X[202];
long long T[202];
long long L;

long long dist(int a, int b)
{
    return min(    abs(X[a] - X[b]),    min(X[a], abs(L - X[a]))   +   min(X[b], abs(L - X[b]))    );
}

int main()
{
    long long inf = 1;
    for(int i = 1; i <= 18; i++) inf = inf * 10LL;

    int N;

    cin >> N >> L;

    for(int i = 1; i <= N; i++) cin >> X[i];
    for(int i = 1; i <= N; i++) cin >> T[i];

    long long dp_left[N+2][N+2][N+2], dp_right[N+2][N+2][N+2];
    for(int i = 0; i <= N+1; i++)
        for(int j = 0; j <= N+1; j++)
            for(int k = 0; k <= N+1; k++)
                dp_left[i][j][k] = dp_right[i][j][k] = inf;
    //minimum time needed to collect k stamps from among j, i+1, ... N, 1, .... i and end up at left/right.

    X[0] = X[N+1] = 0;

    int res = 0;

    dp_left[0][N+1][0] = dp_right[0][N+1][0] = 0;
    for(int k = 0; k <= N; k++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int j = N+1; j > i; j--)
            {
                //don't collect
                if(j < N+1)
                {
                    dp_left[i][j][k] = min(dp_left[i][j][k], dp_left[i][j+1][k] + dist(j, j+1));

                    dp_left[i][j][k] = min(dp_left[i][j][k], dp_right[i][j+1][k] + dist(i, j));
                }

                if(i > 0)
                {
                    dp_right[i][j][k] = min(dp_right[i][j][k], dp_right[i-1][j][k] + dist(i, i-1));

                    dp_right[i][j][k] = min(dp_right[i][j][k], dp_left[i-1][j][k] + dist(i, j));
                }





                if(k == 0) continue;



                //collect
                if(j < N+1)
                {
                    if(dp_left[i][j+1][k-1] + dist(j+1, j) <= T[j])
                        dp_left[i][j][k] = min(dp_left[i][j][k], dp_left[i][j+1][k-1] + dist(j+1, j));

                    if(dp_right[i][j+1][k-1] + dist(i, j) <= T[j])
                        dp_left[i][j][k] = min(dp_left[i][j][k], dp_right[i][j+1][k-1] + dist(i, j));
                }

                if(i > 0)
                {
                    if(dp_right[i-1][j][k-1] + dist(i-1, i) <= T[i])
                        dp_right[i][j][k] = min(dp_right[i][j][k], dp_right[i-1][j][k-1] + dist(i-1, i));

                    if(dp_left[i-1][j][k-1] + dist(i, j) <= T[i])
                        dp_right[i][j][k] = min(dp_right[i][j][k], dp_left[i-1][j][k-1] + dist(i, j));
                }

                if(dp_left[i][j][k] != inf) res = max(res, k);
                if(dp_right[i][j][k] != inf) res = max(res, k);

                // cout << i << ' ' << j << ' ' << k << " -> " << dp_left[i][j][k] << ' ' << dp_right[i][j][k] << '\n';

            }
        }
    }


    cout << res << '\n';
}

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