답안 #78574

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78574 2018-10-06T13:30:09 Z hamzqq9 Sailing Race (CEOI12_race) C++14
55 / 100
3000 ms 9524 KB
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 505
#define MAX 5000000
#define LOG 100
#define KOK 333
using namespace std;

int n,k,x;
int ar[2*N],a[N][N],dp[2*N][2*N],dp2[2*N][2*N];

void f_1() {

	int ans=-1,tut;

	for(int i=1;i<=n;i++) {

		if(dp[i][i+n-1]>ans) {

			ans=dp[i][i+n-1];
			tut=i;

		}

	}

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=n;j++) {

			if(a[i][j] && i!=j) {

				int be=i;
				int en=(i<j?j:j+n-1);
				int last=i+n-1;

				for(int k=be+1;k<=en-1;k++) {

					if(dp2[k][en]>0) {

						for(int l=en+1;l<=last;l++) {

							if(a[ar[k]][ar[l]]) {

								int cur=2+dp2[k][en]+max(dp[l][last],dp[l][en+1]);

								if(cur>ans) {

									ans=cur;
									tut=i;

								}

							}

						}

					}

				}

			}

		}

	}

	printf("%d\n%d\n",ans,tut);

}

void f_0() {

	int ans=-1,tut;

	/*for(int i=1;i<=2*n;i++,puts("")) {

		for(int j=1;j<=2*n;j++) {

			printf("%d ",dp[i][j]);

		}

	}*/

	for(int i=1;i<=n;i++) {

		if(dp[i][i+n-1]>ans) {

			ans=dp[i][i+n-1];
			tut=i;

		}

	}

	printf("%d\n%d\n",ans,tut);

}

void do_1() {

	for(int i=1;i<=2*n;i++) for(int j=1;j<=2*n;j++) dp2[i][j]=-inf;

	for(int i=1;i<=2*n;i++) dp2[i][i]=0;

	for(int len=2;len<=n;len++) {

		for(int i=1;i<=2*n;i++) {

			int beg=i-len+1;
			int en=i+len-1;

			if(beg>=1) {

				for(int j=beg;j<i;j++) {

					if(a[ar[j]][ar[i]]) umax(dp2[i][beg],dp2[j][beg]+1);

				}

			}

			if(en<=2*n) {

				for(int j=i+1;j<=en;j++) {

					if(a[ar[j]][ar[i]]) umax(dp2[i][en],dp2[j][en]+1);

				}

			}

		}

	}

}

void do_0() {

	for(int len=2;len<=n;len++) {

		for(int i=1;i<=2*n;i++) {

			int beg=i-len+1;
			int en=i+len-1;

			if(beg>=1) {

				for(int j=beg;j<i;j++) {

					if(a[ar[i]][ar[j]]) umax(dp[i][beg],max(dp[j][beg],dp[j][i-1])+1);

				}

			}

			if(en<=2*n) {

				for(int j=i+1;j<=en;j++) {

					if(a[ar[i]][ar[j]]) umax(dp[i][en],max(dp[j][en],dp[j][i+1])+1);

				}

			}
		
		}

	}

}

int main() {
	
	//freopen("input.txt","r",stdin);

	scanf("%d %d",&n,&k);

	for(int i=1;i<=n;i++) {

		do {

			scanf("%d",&x);

			if(x==0) break ;

			a[i][x]=1;

		} while(1);

	}

	for(int i=1;i<=n;i++) ar[i]=ar[i+n]=i;

	do_0();
	do_1();

	if(k==0) f_0();
	else f_1();

}

Compilation message

race.cpp: In function 'int main()':
race.cpp:196:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
race.cpp:202:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 884 KB Output isn't correct
3 Incorrect 3 ms 1192 KB Output isn't correct
4 Correct 4 ms 1192 KB Output is correct
5 Correct 5 ms 1552 KB Output is correct
6 Correct 8 ms 1572 KB Output is correct
7 Correct 9 ms 1716 KB Output is correct
8 Incorrect 12 ms 1972 KB Output isn't correct
9 Correct 18 ms 2208 KB Output is correct
10 Correct 14 ms 2396 KB Output is correct
11 Correct 25 ms 2396 KB Output is correct
12 Correct 234 ms 4120 KB Output is correct
13 Incorrect 456 ms 5980 KB Output isn't correct
14 Correct 496 ms 7632 KB Output is correct
15 Execution timed out 3051 ms 9436 KB Time limit exceeded
16 Execution timed out 3023 ms 9440 KB Time limit exceeded
17 Execution timed out 3050 ms 9440 KB Time limit exceeded
18 Correct 865 ms 9524 KB Output is correct
19 Execution timed out 3074 ms 9524 KB Time limit exceeded
20 Execution timed out 3055 ms 9524 KB Time limit exceeded