Submission #205324

#	Time	Username	Problem	Language	Result	Execution time	Memory
205324		TadijaSebez	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	146 ms	135544 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=9e18;
const int N=205;
void ckmn(ll &a,ll b){a=min(a,b);}
ll dp[N][N][2][N];
int x[N],t[N];
int main(){
	int n,L;
	scanf("%i %i",&n,&L);
	for(int i=1;i<=n;i++)scanf("%i",&x[i]);
	for(int i=1;i<=n;i++)scanf("%i",&t[i]);
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)for(int k=0;k<2;k++)for(int o=0;o<N;o++)dp[i][j][k][o]=inf;
	dp[0][n+1][0][0]=0;
	for(int sz=n+1;sz>1;sz--){
		for(int i=0;i<=n+1-sz;i++){
			int j=i+sz;
			for(int k=0;k<=n;k++){
				if(dp[i][j][0][k]<inf){
					ll tme=dp[i][j][0][k]+x[i+1]-x[i];
					ckmn(dp[i+1][j][0][k+(tme<=t[i+1])],tme);
					tme=dp[i][j][0][k]+x[i]+L-x[j-1];
					ckmn(dp[i][j-1][1][k+(tme<=t[j-1])],tme);
				}
				if(dp[i][j][1][k]<inf){
					ll tme=dp[i][j][1][k]+x[i+1]+L-x[j];
					ckmn(dp[i+1][j][0][k+(tme<=t[i+1])],tme);
					tme=dp[i][j][1][k]+x[j]-x[j-1];
					ckmn(dp[i][j-1][1][k+(tme<=t[j-1])],tme);
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++)for(int k=1;k<=n;k++)if(dp[i][i+1][0][k]<inf || dp[i][i+1][1][k]<inf)ans=max(ans,k);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&L);
  ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&x[i]);
                       ~~~~~^~~~~~~~~~~~
ho_t3.cpp:13:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%i",&t[i]);
                       ~~~~~^~~~~~~~~~~~

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