Submission #593396

#	Time	Username	Problem	Language	Result	Execution time	Memory
593396		Hanksburger	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	88 ms	33276 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
int dp[205][205][205][2], x[205], t[205], n, l;
int d(int i, int j)
{
    return min(abs(x[i]-x[j]), l-abs(x[i]-x[j]));
}
int f(int l, int r, int c, int s)
{
    if (!c)
        return 1e9;
    if (c>r-l+1)
        return -1e9;
    if (dp[l][r][c][s]!=-1e9)
        return dp[l][r][c][s];
    int ind, ans=-1e9;
    if (s)
        ind=r+1;
    else
        ind=l-1;
    ans=max(ans, f(l+1, r, c, 0)-d(ind, l));
    ans=max(ans, f(l, r-1, c, 1)-d(ind, r));
    ans=max(ans, min(f(l+1, r, c-1, 0), t[l])-d(ind, l));
    ans=max(ans, min(f(l, r-1, c-1, 1), t[r])-d(ind, r));
    dp[l][r][c][s]=ans;
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> l;
    for (int i=1; i<=n; i++)
        cin >> x[i];
    for (int i=1; i<=n; i++)
        cin >> t[i];
    for (int i=1; i<=n; i++)
        for (int j=i; j<=n; j++)
            for (int k=1; k<=j-i+1; k++)
            dp[i][j][k][0]=dp[i][j][k][1]=-1e9;
    for (int i=1; i<=n; i++)
    {
        if (f(1, n, i, 0)<0)
        {
            cout << i-1;
            return 0;
        }
    }
    cout << n;
    return 0;
}

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