Submission #438887

#	Time	Username	Problem	Language	Result	Execution time	Memory
438887		Snowfall	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	131 ms	130744 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
long long arr[205][205][205][2];
int a[205],b[205];
main()
{
	int t,p;
    scanf("%d%d",&t,&p);
    queue<pair<int,pair<int,int> > >q;
    for(int i = 1;i <= t;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 1;i <= t;i++)
    {
        scanf("%d",&b[i]);
    }
    for(int i = 0;i <= t;i++)
    {
        for(int j = 0;j <= t;j++)
        {
            for(int k = 0;k <= t;k++)
            {
                for(int l = 0;l < 2;l++)
                arr[i][j][k][l]=1e18;
            }
        }
    }
    a[t+1]=p;
    arr[0][0][0][0]=0;
    arr[0][0][0][1]=0;
    for(int i = 0;i <= t;i++)
    {
        for(int j = 0;j+i <= t;j++)
        {
            for(int k = 0;k <= i+j;k++)
            {
                if(i+j+1<=t)
                {
                    if(arr[i][j][k][0]+a[i+1]-a[i]<=b[i+1])
                    {
                        arr[i+1][j][k+1][0]=min(arr[i+1][j][k+1][0],arr[i][j][k][0]+a[i+1]-a[i]);
                    }
                    else
                    {
                        arr[i+1][j][k][0]=min(arr[i+1][j][k][0],arr[i][j][k][0]+a[i+1]-a[i]);
                    }

                    if(arr[i][j][k][1]+a[t-j+1]-a[t-j]<=b[t-j])
                    {
                        arr[i][j+1][k+1][1]=min(arr[i][j+1][k+1][1],arr[i][j][k][1]+a[t-j+1]-a[t-j]);
                    }
                    else
                    {
                        arr[i][j+1][k][1]=min(arr[i][j+1][k][1],arr[i][j][k][1]+a[t-j+1]-a[t-j]);
                    }

                    if(arr[i][j][k][0]+a[i]+p-a[t-j]<=b[t-j])
                    {
                        arr[i][j+1][k+1][1]=min(arr[i][j+1][k+1][1],arr[i][j][k][0]+a[i]+p-a[t-j]);
                    }
                    else
                    {
                        arr[i][j+1][k][1]=min(arr[i][j+1][k][1],arr[i][j][k][0]+a[i]+p-a[t-j]);
                    }

                    if(arr[i][j][k][1]+p-a[t-j+1]+a[i+1]<=b[i+1])
                    {
                        arr[i+1][j][k+1][0]=min(arr[i+1][j][k+1][0],arr[i][j][k][1]+p-a[t-j+1]+a[i+1]);
                    }
                    else
                    {
                        arr[i+1][j][k][0]=min(arr[i+1][j][k][0],arr[i][j][k][1]+p-a[t-j+1]+a[i+1]);
                    }
                }
            }
        }
    }
    int mx=0;
    for(int i = 0;i <= t;i++)
    {
        for(int j = 0;j+i <= t;j++)
        {
            for(int k = 0;k <= i+j;k++)
            {
                for(int l = 0;l < 2;l++)
                {
                    if(arr[i][j][k][l]!=1e18)
                    mx=max(mx,k);
                }
            }
        }
    }
    printf("%d",mx);
}

Compilation message (stderr)

ho_t3.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 | main()
      | ^~~~
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     scanf("%d%d",&t,&p);
      |     ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
ho_t3.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d",&b[i]);
      |         ~~~~~^~~~~~~~~~~~

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