oj.uz

Submission #286961

# Submission time Handle Problem Language Result Execution time Memory
286961 2020-08-31T08:03:43 Z arnold518 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 512 KB 
#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(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(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(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(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);

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

Compilation message

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Halted 0 ms 0 KB -