Submission #78575

# Submission time Handle Problem Language Result Execution time Memory
78575 2018-10-06T13:33:19 Z hamzqq9 Sailing Race (CEOI12_race) C++14
40 / 100
3000 ms 9596 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;

								}

							}

						}

					}

				}

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

					if(dp2[k][en]) {

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

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

								int cur=2+dp2[k][n]+max(dp[l][be+1],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:221: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:227:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 3 ms 884 KB Output isn't correct
3 Incorrect 3 ms 1064 KB Output isn't correct
4 Incorrect 5 ms 1080 KB Output isn't correct
5 Correct 5 ms 1380 KB Output is correct
6 Incorrect 10 ms 1528 KB Output isn't correct
7 Correct 10 ms 1656 KB Output is correct
8 Incorrect 14 ms 1912 KB Output isn't correct
9 Correct 16 ms 2096 KB Output is correct
10 Correct 20 ms 2352 KB Output is correct
11 Correct 24 ms 2468 KB Output is correct
12 Incorrect 375 ms 4048 KB Output isn't correct
13 Incorrect 757 ms 5968 KB Output isn't correct
14 Correct 486 ms 7788 KB Output is correct
15 Execution timed out 3052 ms 9580 KB Time limit exceeded
16 Execution timed out 3049 ms 9580 KB Time limit exceeded
17 Execution timed out 3042 ms 9580 KB Time limit exceeded
18 Correct 964 ms 9596 KB Output is correct
19 Execution timed out 3039 ms 9596 KB Time limit exceeded
20 Execution timed out 3052 ms 9596 KB Time limit exceeded