Submission #900164

#	Time	Username	Problem	Language	Result	Execution time	Memory
900164		andrei_iorgulescu	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	40 ms	134020 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

#define int long long

int inf = 1e18;

int n,l,x[205],t[205];
int dp[205][205][205][2];
int sp[205];

int dist(int px,int py)
{
    return x[py] - x[px];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    x[n + 1] = l;
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int q = 0; q <= n; q++)
                for (int c = 0; c < 2; c++)
                    dp[i][j][q][c] = inf;
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = 0; j <= n - 1 - i; j++)
        {
            for (int k = 0; k <= i + j; k++)
            {
                //cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << endl;
                //cout << i << ' ' << j << ' ' << k << ' ';
                int t0 = dp[i][j][k][0] + dist(n - i,n - i + 1);
                if (t0 <= t[n - i])
                    dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0],t0);
                else
                    dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0],t0);
                int t1 = dp[i][j][k][0] + l - dist(j + 1,n - i + 1);
                if (t1 <= t[j + 1])
                    dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1],t1);
                else
                    dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1],t1);
                int t2 = dp[i][j][k][1] + l - dist(j,n - i);
                if (t2 <= t[n - i])
                    dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0],t2);
                else
                    dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0],t2);
                int t3 = dp[i][j][k][1] + dist(j,j + 1);
                if (t3 <= t[j + 1])
                    dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1],t3);
                else
                    dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1],t3);
                //cout << t0 << ' ' << t1 << ' ' << t2 << ' ' << t3 << endl;
            }
        }
    }
    for (int i = n; i >= 1; i--)
    {
        bool pot = false;
        for (int j = 0; j <= n; j++)
        {
            int q = n - j;
            if (dp[j][q][i][0] < inf or dp[j][q][i][1] < inf)
                pot = true;
        }
        if (pot == true)
        {
            cout << i;
            return 0;
        }
    }
    cout << 0;
    return 0;
}

/**
presupun ca exista punctul 0, apoi in dreapta punctele sunt 1,2,...,n iar in stanga sunt n,n-1,...,1
**/

/**
dp[i][j][k][0/1] -> care este timpul minim la care sa fiu la i in stanga (0) sau j in dreapta (1) a.i am acoperit interv [i j] si am k stamp-uri
{i,j,k,0} -> {i + 1,j,k sau k + 1 in functie de timp,0} sau {i,j + 1,k sau k + 1 in functie de timp,1}
{i,j,k,1} -> {i + 1,j,k sau k + 1 in functie de timp,0} sau {i,j + 1,k sau k + 1 in functie de timp,1}
**/

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