oj.uz

Submission #127862

# Submission time Handle Problem Language Result Execution time Memory
127862 2019-07-10T07:29:11 Z 이온조(#3109) JOI15_aaqqz (JOI15_aaqqz) C++14
0 / 100
 3 ms 508 KB 
#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(D[L-1][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;
			if(sr) while(D[L-1][R+1]) --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);
	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

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:119: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:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 508 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 508 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Incorrect 2 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -