Submission #563668

#	Time	Username	Problem	Language	Result	Execution time	Memory
563668		groshi	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	74 ms	67516 KiB

ho_t3

#include<iostream>
#include<vector>
using namespace std;
vector<int> Q;
int dp[210][210][210][2];
int t[300],x[400];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l;
    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=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            for(int k=0;k<=n;k++)
            {
                dp[i][j][k][0]=1000000000;
                dp[i][j][k][1]=1000000000;
            }
    x[n+1]=l;
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    for(int k=0;k<=n;k++)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j+i<n;j++)
            {
                int ile=x[i]+(l-x[n+1-j]);
                dp[i][j][k][0]=min(dp[i][j][k][1]+ile,dp[i][j][k][0]);
                dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j][k][0]+ile);
                int do_lewej=dp[i][j][k][0]+(x[i+1]-x[i]);
                //cout<<do_lewej<<"\n";
                if(do_lewej<=t[i+1])
                    dp[i+1][j][k+1][0]=min(dp[i+1][j][k+1][0],do_lewej);
                else dp[i+1][j][k][0]=min(dp[i+1][j][k][0],do_lewej);
                int do_prawej=dp[i][j][k][1]+(x[n+1-j]-x[n+1-j-1]);
                //cout<<do_prawej<<"\n";
                if(do_prawej<=t[n+1-j-1])
                    dp[i][j+1][k+1][1]=min(dp[i][j+1][k+1][1],do_prawej);
                else dp[i][j+1][k][1]=min(dp[i][j+1][k][1],do_prawej);
            }
        }
    }
    int wynik=0;
    for(int i=0;i<=n;i++)
        for(int j=!i;j+i<=n;j++)
             for(int k=0;k<=n;k++)
                 if(dp[i][j][k][0]!=1e9 || dp[i][j][k][1]!=1e9)
                    wynik=max(wynik,k);
    cout<<wynik;
    return 0;
}

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