oj.uz

Submission #375299

# Submission time Handle Problem Language Result Execution time Memory
375299 2021-03-09T07:03:25 Z YJU Sailing Race (CEOI12_race) C++14
15 / 100
 459 ms 3564 KB 
#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<<"\n";
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0


*/

Subtask #1
15.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 Incorrect 2 ms 620 KB Output isn't 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 Incorrect 6 ms 876 KB Output isn't correct
10 Correct 4 ms 1004 KB Output is correct
11 Incorrect 8 ms 1004 KB Output isn't correct
12 Incorrect 29 ms 1516 KB Output isn't correct
13 Incorrect 77 ms 2276 KB Output isn't correct
14 Incorrect 167 ms 2812 KB Output isn't correct
15 Incorrect 383 ms 3564 KB Output isn't correct
16 Incorrect 413 ms 3436 KB Output isn't correct
17 Incorrect 382 ms 3436 KB Output isn't correct
18 Incorrect 287 ms 3308 KB Output isn't correct
19 Incorrect 457 ms 3564 KB Output isn't correct
20 Incorrect 459 ms 3436 KB Output isn't correct