Submission #128016

#	Time	Username	Problem	Language	Result	Execution time	Memory
128016		onjo0127	AAQQZ (JOI15_aaqqz)	C++11	100 / 100	1101 ms	9352 KiB

aaqqz

#include <bits/stdc++.h>
using namespace std;

int N, C, A[3009], U[3009], ans;
bool D[3009][3009];

void go(int s, int e) {
	if(s < 0 || N < e || s > e) return;
	
	int p = -1;
	vector<int> T;
	for(int i=s-1; i>=1; i--) {
		if(p == -1 || p <= A[i]) {
			T.push_back(A[i]);
			p = A[i];
		}
		else break;
	}
	
	int l = 0, r = (int)T.size() - 1;
	while(l <= r) {
		int m = l+r >> 1;
		vector<int> H(C+1, 0);
		for(int i=0; i<=m; i++) ++H[T[i]];
		int c = 0;
		bool f = 1, sr = 1;
		for(int i=e+1; i<=N && c<=m; i++) {
			if(H[A[i]]) {
				--H[A[i]];
				++c;
			}
			else {
				sr = 0;
				if(A[i] < T[m]) f = 0;
			}
		}
		f &= (c > m);

		if(f) {
			int L = s - m - 1, R = e + m + 1;
			if(sr) while(A[L-1] == A[R+1]) --L, ++R;
			ans = max(ans, R-L+1);
		}

		if(f) l = m+1;
		else r = m-1;
	}
}

void Do(int s, bool SR) {
	int p = -1;
	vector<int> T;
	for(int i=s-1; i>=1; i--) {
		if(p == -1 || p <= A[i]) {
			T.push_back(A[i]);
			p = A[i];
		}
		else break;
	}
	if(T.empty()) return;

	int mn = T[0];
	for(int i=s; i<=N; i++) if(T[0] > A[i]) {mn = A[i]; break;}

	int l = 0, r = (int)T.size() - 1;
	while(l <= r) {
		int m = l+r >> 1;
		vector<int> H(C+1, 0);
		for(int i=0; i<=m; i++) ++H[T[i]];
		int c = 0, mnc = 0;
		bool f = 1, sr = 1;
		for(int i=s; i<=N; i++) {
			if(H[A[i]]) {
				--H[A[i]];
				++c;
			}
			else if(A[i] == mn) ++mnc;
			else {
				if(sr && SR && c > m) break;
				sr = 0;
				if(A[i] < T[m]) break;
			}
		}
		f &= (c > m);

		if(f) {
			int L = s - m - 1, R = s + m + mnc;
			// printf("[%d, %d]\n", L, R);
			if(sr) while(A[L-1] == A[R+1]) --L, ++R;
			// printf("s: %d, SR: %d, sr: %d, m: %d, [%d, %d]\n", s, SR, sr, m, L, R);
			ans = max(ans, R-L+1);
		}

		if(f) l = m+1;
		else r = m-1;
	}
}

void solve() {
	for(int i=N; i>=1; i--) {
		for(int j=i; j<=N; j++) {
			if(i+1 >= j && A[i] == A[j]) D[i][j] = 1;
			else if(D[i+1][j-1] && A[i] == A[j]) D[i][j] = 1;
			else D[i][j] = 0;
			if(D[i][j]) ans = max(ans, j-i+1);
		}
	}
	for(int i=1; i<=N; i++) {
		int l = i, r = i;
		while(D[l-1][r+1]) --l, ++r;
		go(l, r);
		l = i, r = i-1;
		while(D[l-1][r+1]) --l, ++r;
		go(l, r);
		Do(i, 0);
		Do(i, 1);
	}
}

int main() {
	scanf("%d%d",&N,&C);
	A[0] = 1e9;
	for(int i=1; i<=N; i++) {
		scanf("%d",&A[i]);
		++U[A[i]];
	}
	for(int i=1; i<=C; i++) ans = max(ans, U[i]);
	solve();
	reverse(A+1, A+N+1);
	for(int i=1; i<=N; i++) A[i] = C - A[i] + 1;
	solve();
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

aaqqz.cpp: In function 'void go(int, int)':
aaqqz.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l+r >> 1;
           ~^~
aaqqz.cpp: In function 'void Do(int, bool)':
aaqqz.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l+r >> 1;
           ~^~
aaqqz.cpp: In function 'int main()':
aaqqz.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&C);
  ~~~~~^~~~~~~~~~~~~~
aaqqz.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90