Submission #375300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
375300	2021-03-09T07:04:14 Z	YJU	Sailing Race (CEOI12_race)	C++14	40 / 100	468 ms	3440 KB

race

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=5e2+5;
const ll MOD=1e9+7;
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,type,grid[N][N],x,dp[N][N][2];

ll ansm,anss;

void upd(ll ans,ll id){
	if(ans>=ansm){
		ansm=ans,anss=id;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>type;
	REP(i,n){
		while(1){
            cin>>x;
            if(x==0)break;
            grid[i][x-1]=1;
		}
	}
	for(int len=2;len<n;len++){
        for(int i=0,j=(i+len>=n?i+len-n:i+len);i<n;i++,j=(j+1>=n?0:j+1)){
            for(int k=(i+1>=n?0:i+1);k!=j;k=(k+1>=n?0:k+1)){
				//i,j,0 means boat is now at i
				//i,j,1,means boat is now at j
                dp[i][j][0]=max(dp[i][j][0],(grid[i][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
                dp[i][j][1]=max(dp[i][j][1],(grid[j][k]?1+max(dp[i][k][1],dp[k][j][0]):0));
            }
        }
	}
	REP(i,n)REP(j,n){
		if(i==j)continue;
		if(grid[i][j]){
			//cout<<i<<" "<<j<<" "<<dp[i][j][1]<<" "<<dp[j][i][0]<<"\n";
            upd(max(dp[i][j][1],dp[j][i][0])+1,i);
		}
	}
	cout<<ansm<<"\n"<<anss+1<<"\n";
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0


*/

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Incorrect	1 ms	492 KB	Output isn't correct
3	Incorrect	1 ms	492 KB	Output isn't correct
4	Incorrect	1 ms	620 KB	Output isn't correct
5	Correct	2 ms	620 KB	Output is correct
6	Incorrect	2 ms	748 KB	Output isn't correct
7	Correct	3 ms	748 KB	Output is correct
8	Incorrect	3 ms	876 KB	Output isn't correct
9	Correct	8 ms	876 KB	Output is correct
10	Correct	4 ms	876 KB	Output is correct
11	Correct	8 ms	876 KB	Output is correct
12	Incorrect	30 ms	1644 KB	Output isn't correct
13	Incorrect	85 ms	2284 KB	Output isn't correct
14	Correct	167 ms	2668 KB	Output is correct
15	Incorrect	382 ms	3436 KB	Output isn't correct
16	Incorrect	417 ms	3328 KB	Output isn't correct
17	Incorrect	403 ms	3440 KB	Output isn't correct
18	Correct	344 ms	3440 KB	Output is correct
19	Incorrect	468 ms	3436 KB	Output isn't correct
20	Incorrect	463 ms	3368 KB	Output isn't correct