Submission #286980

#	Time	Username	Problem	Language	Result	Execution time	Memory
286980		arnold518	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	83 ms	68908 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 200;
const ll INF = 1e18;

int N, L, X[MAXN+10], T[MAXN+10], ans;
ll dp1[MAXN+10][MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10][MAXN+10];

int main()
{
	scanf("%d%d", &N, &L);
	for(int i=1; i<=N; i++) scanf("%d", &X[i]);
	for(int i=1; i<=N; i++) scanf("%d", &T[i]);
	X[N+1]=L;

	for(int i=0; i<=N; i++)
	{
		for(int j=N+1; j>=i+1; j--)
		{
			for(int k=0; k<=N; k++)
			{
				if(i==0 && j==N+1)
				{
					if(k==0) dp1[i][j][k]=dp2[i][j][k]=0;
					else dp1[i][j][k]=dp2[i][j][k]=INF;
					continue;
				}
				ll t=INF;
				if(i>=1)
				{
					if(k && dp1[i-1][j][k-1]+X[i]-X[i-1]<=T[i]) t=min(t, dp1[i-1][j][k-1]+X[i]-X[i-1]);
					if(dp1[i-1][j][k]+X[i]-X[i-1]>T[i]) t=min(t, dp1[i-1][j][k]+X[i]-X[i-1]);

					if(k && dp2[i-1][j][k-1]+L-X[j]+X[i]<=T[i]) t=min(t, dp2[i-1][j][k-1]+L-X[j]+X[i]);
					if(dp2[i-1][j][k]+L-X[j]+X[i]>T[i]) t=min(t, dp2[i-1][j][k]+L-X[j]+X[i]);
				}
				dp1[i][j][k]=t;

				t=INF;
				if(j<=N)
				{
					if(k && dp2[i][j+1][k-1]+X[j+1]-X[j]<=T[j]) t=min(t, dp2[i][j+1][k-1]+X[j+1]-X[j]);
					if(dp2[i][j+1][k]+X[j+1]-X[j]>T[j]) t=min(t, dp2[i][j+1][k]+X[j+1]-X[j]);

					if(k && dp1[i][j+1][k-1]+X[i]+L-X[j]<=T[j]) t=min(t, dp1[i][j+1][k-1]+X[i]+L-X[j]);
					if(dp1[i][j+1][k]+X[i]+L-X[j]>T[j]) t=min(t, dp1[i][j+1][k]+X[i]+L-X[j]);
				}
				dp2[i][j][k]=t;

				if(dp1[i][j][k]!=INF) ans=max(ans, k);
				if(dp2[i][j][k]!=INF) ans=max(ans, k);

				//if(j==11) printf("%d %d %d : %lld %lld\n", i, j, k, dp1[i][j][k], dp2[i][j][k]);
			}
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d%d", &N, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:17:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  for(int i=1; i<=N; i++) scanf("%d", &X[i]);
      |                          ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:18:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |  for(int i=1; i<=N; i++) scanf("%d", &T[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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