Submission #1172187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172187		AlgorithmWarrior	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	73 ms	130700 KiB

ho_t3

#include <bits/stdc++.h>
#define MAX 205

using namespace std;

long long dp[MAX][MAX][MAX][2];
/// dp[i][j][k][0/1] = timpul minim sa parcurgem primele i clockwise
/// si primele j counterclockwise colectand cel putin k statui
/// si avand 1 (daca ne oprim la al i-lea clockwise)
/// sau 0 (daca ne oprim la al j-lea counterclockwise)
int dist[MAX];
int limit[MAX];
int N,L;
int ans;

void read()
{
    cin>>N>>L;
    int i;
    for(i=1;i<=N;++i)
        cin>>dist[i];
    for(i=1;i<=N;++i)
        cin>>limit[i];
    dist[N+1]=L;
    dist[N+2]=L;
}

void minself(long long& x,long long y)
{
    x=min(x,y);
}

void calc_dp()
{
    int i,j,k;
    for(i=0;i<=N;++i)
        for(j=0;j<=N;++j)
            for(k=0;k<=N;++k)
                dp[i][j][k][0]=dp[i][j][k][1]=2e18;
    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    for(i=0;i<=N;++i)
        for(j=0;j<=N-i;++j)
        {
            if(!i && !j)
                continue;
            int totaldist=dist[i]+L-dist[N-j+1];
            int dist1=dist[i]-dist[i-1];
            int dist0=dist[N-j+2]-dist[N-j+1];
            dp[i][j][0][1]=2LL*(L-dist[N-j+1])+dist[i];
            dp[i][j][0][0]=2LL*dist[i]+L-dist[N-j+1];
            for(k=1;k<=i+j;++k)
            {
                if(i)
                {
                    minself(dp[i][j][k][1],dp[i-1][j][k][1]+dist1);
                    if(dp[i-1][j][k-1][1]+dist1<=limit[i])
                        minself(dp[i][j][k][1],dp[i-1][j][k-1][1]+dist1);
                }
                if(j)
                {
                    minself(dp[i][j][k][0],dp[i][j-1][k][0]+dist0);
                    if(dp[i][j-1][k-1][0]+dist0<=limit[N-j+1])
                        minself(dp[i][j][k][0],dp[i][j-1][k-1][0]+dist0);
                }
                minself(dp[i][j][k][0],dp[i][j][k][1]+totaldist);
                minself(dp[i][j][k][1],dp[i][j][k][0]+totaldist);
            }
        }
}

void debug()
{
    int i,j,k,l;
    for(i=0;i<=N;++i)
        for(j=0;j<=N;++j)
            for(k=0;k<=N;++k)
                for(l=0;l<2;++l)
                    if(dp[i][j][k][l]<2e9)
                        cout<<dp[i][j][k][l]<<' '<<i<<' '<<j<<' '<<k<<' '<<l<<'\n';
}

void get_answer()
{
    int i,j,k,l;
    for(i=0;i<=N;++i)
        for(j=0;j<=N-i;++j)
            for(k=0;k<=i+j;++k)
                for(l=0;l<2;++l)
                    if(dp[i][j][k][l]<2e18)
                        ans=max(ans,k);
}

void write()
{
    cout<<ans;
}

int main()
{
    read();
    calc_dp();
    get_answer();
    write();
    return 0;
}

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