oj.uz

답안 #375300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
375300 2021-03-09T07:04:14 Z YJU Sailing Race (CEOI12_race) C++14
40 / 100
 468 ms 3440 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+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

# 결과 실행 시간 메모리 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