Submission #265290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265290	2020-08-14T14:58:02 Z	TadijaSebez	Sailing Race (CEOI12_race)	C++11	75 / 100	3000 ms	3320 KB

race

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void ckmx(int&x,int y){x=max(x,y);}
const int N=505;
vector<int> E[N];
int dp[N][N][2],n,k,tmp[N];
bool was[N][N][2];
int on(int l,int r,int v){
	return (l<=r&&l<=v&&r>=v)||(l>r&&(v<=r||v>=l));
}
int DP(int l,int r,int side){
	if(was[l][r][side])return dp[l][r][side];
	int u=side==0?l:r;
	was[l][r][side]=1;
	int L=side==0?(l==n?1:l+1):l;
	int R=side==1?(r==1?n:r-1):r;
	for(int v:E[u]){
		if(on(l,r,v)){
			ckmx(dp[l][r][side],1+max(DP(L,v,1),DP(v,R,0)));
		}
	}
	return dp[l][r][side];
}
int main(){
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++){
		while(1){
			int j;
			scanf("%i",&j);
			if(j==0)break;
			E[i].pb(j);
		}
	}
	int ans=-1,idx=0;
	for(int i=1;i<=n;i++){
		int now=DP(i,i==1?n:i-1,0);
		if(k==1){
			auto nxt=[&](int x){return x==n?1:x+1;};
			auto pre=[&](int x){return x==1?n:x-1;};
			for(int j:E[i]){
				for(int l=1;l<=n;l++)tmp[l]=0;
				tmp[j]=1;
				for(int l=j;l!=i;l=nxt(l)){
					for(int r:E[l])if(r!=i&&r!=j){
						if(on(i,j,r))ckmx(now,tmp[l]+1+max(DP(nxt(i),r,1),DP(r,pre(j),0)));
						else ckmx(tmp[r],tmp[l]+1);
					}
				}
				for(int l=j;l!=i;l=pre(l)){
					for(int r:E[l])if(r!=i&&r!=j){
						if(on(j,i,r))ckmx(now,tmp[l]+1+max(DP(nxt(j),r,1),DP(r,pre(i),0)));
						else ckmx(tmp[r],tmp[l]+1);
					}
				}
			}
		}
		if(now>ans)ans=now,idx=i;
	}
	printf("%i\n%i\n",ans,idx);
	return 0;
}

Compilation message

race.cpp: In function 'int main()':
race.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  scanf("%i %i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
race.cpp:30:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |    scanf("%i",&j);
      |    ~~~~~^~~~~~~~~

Subtask #1

75.0 / 100.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	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	8 ms	640 KB	Output is correct
7	Correct	4 ms	896 KB	Output is correct
8	Correct	8 ms	768 KB	Output is correct
9	Correct	5 ms	896 KB	Output is correct
10	Correct	14 ms	896 KB	Output is correct
11	Correct	7 ms	896 KB	Output is correct
12	Correct	247 ms	1408 KB	Output is correct
13	Correct	382 ms	1940 KB	Output is correct
14	Correct	63 ms	2432 KB	Output is correct
15	Execution timed out	3040 ms	3064 KB	Time limit exceeded
16	Execution timed out	3099 ms	3192 KB	Time limit exceeded
17	Execution timed out	3098 ms	3064 KB	Time limit exceeded
18	Correct	77 ms	2936 KB	Output is correct
19	Execution timed out	3090 ms	3320 KB	Time limit exceeded
20	Execution timed out	3097 ms	3192 KB	Time limit exceeded