Submission #201273

#	Time	Username	Problem	Language	Result	Execution time	Memory
201273		arnold518	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	75 ms	67960 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 = 1e16;

int N, ans;
ll L, X[MAXN+10], T[MAXN+10];
ll dp[MAXN+10][MAXN+10][MAXN+10][2];

int main()
{
	int i, j, k;

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

	for(i=0; i<=N; i++)
	{
		for(j=N+1; j>i; j--)
		{
			for(k=0; k<=N; k++)
			{
				if(i==0 && j==N+1 && k==0) continue;
				dp[i][j][k][0]=dp[i][j][k][1]=INF;

				if(i-1>=0)
				{
					dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k][0]+X[i]-X[i-1]);
					dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k][1]+L-X[j]+X[i]);
					if(k && dp[i-1][j][k-1][0]+X[i]-X[i-1]<=T[i]) dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k-1][0]+X[i]-X[i-1]);
					if(k && dp[i-1][j][k-1][1]+L-X[j]+X[i]<=T[i]) dp[i][j][k][0]=min(dp[i][j][k][0], dp[i-1][j][k-1][1]+L-X[j]+X[i]);
				}

				if(j+1<=N+1)
				{
					dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j+1][k][1]+X[j+1]-X[j]);
					dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j+1][k][0]+L-X[j]+X[i]);
					if(k && dp[i][j+1][k-1][1]+X[j+1]-X[j]<=T[j]) dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j+1][k-1][1]+X[j+1]-X[j]);
					if(k && dp[i][j+1][k-1][0]+L-X[j]+X[i]<=T[j]) dp[i][j][k][1]=min(dp[i][j][k][1], dp[i][j+1][k-1][0]+L-X[j]+X[i]);
				}

				if(dp[i][j][k][0]!=INF) ans=max(ans, k);
				if(dp[i][j][k][1]!=INF) ans=max(ans, k);
			}
		}
	}
	printf("%d", ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:20:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=1; i<=N; i++) scanf("%lld", &X[i]); X[N+1]=L;
  ^~~
ho_t3.cpp:20:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=1; i<=N; i++) scanf("%lld", &X[i]); X[N+1]=L;
                                            ^
ho_t3.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~
ho_t3.cpp:20:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &X[i]); X[N+1]=L;
                      ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:21:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &T[i]);
                      ~~~~~^~~~~~~~~~~~~~~

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