Submission #554918

#	Time	Username	Problem	Language	Result	Execution time	Memory
554918		rainboy	AAQQZ (JOI15_aaqqz)	C11	100 / 100	1008 ms	63304 KiB

aaqqz

#include <stdio.h>
#include <string.h>

#define N	3000
#define C	3000

int max(int a, int b) { return a > b ? a : b; }

int pp[N][C], dp[N][N];

int count(int l, int r, int a, int b) {
	return l > r || a > b ? 0 : pp[r][b] - (a == 0 ? 0 : pp[r][a - 1]) - (l == 0 ? 0 : pp[l - 1][b] - (a == 0 ? 0 : pp[l - 1][a - 1]));
}

int solve(int *aa, int n, int c) {
	int i, i_, j_, j, j1, j2, ij, a, k, ans;

	for (i = 0; i < n; i++)
		memset(pp[i], 0, c * sizeof *pp[i]);
	for (i = 0; i < n; i++)
		pp[i][aa[i]]++;
	for (i = 0; i < n; i++)
		for (a = 1; a < c; a++)
			pp[i][a] += pp[i][a - 1];
	for (a = 0; a < c; a++)
		for (i = 1; i < n; i++)
			pp[i][a] += pp[i - 1][a];
	for (i = 0; i < n; i++)
		for (j = i; j < n; j++)
			dp[i][j] = aa[i] != aa[j] ? 0 : (i > 0 && j + 1 < n ? dp[i - 1][j + 1] : 0) + 1;
	ans = 0;
	for (a = 0; a < c; a++)
		ans = max(ans, count(0, n - 1, a, a));
	for (ij = 0; ij <= (n - 1) + (n - 1); ij++) {
		i = ij / 2, j = ij - i;
		while (i >= 0 && j < n && aa[i] == aa[j])
			i--, j++;
		ans = max(ans, j - i - 1);
		for (i_ = i, j_ = j, j1 = j, j2 = n - 1; i_ >= 0 && j_ < n; i_--, j_++) {
			if (i_ < i && aa[i_] < aa[i_ + 1])
				break;
			k = count(i_, i, aa[i_], aa[i_]);
			while (j1 < n && count(j, j1, aa[i_], aa[i_]) < k)
				j1++;
			k = count(i_, i, 0, aa[i_] - 1);
			while (j2 >= j && count(j, j2, 0, aa[i_] - 1) > k)
				j2--;
			if (j1 <= j2) {
				ans = max(ans, j_ - i_ + 1);
				if (j1 <= j_ && j_ <= j2)
					ans = max(ans, j_ - i_ + 1 + (i_ > 0 && j_ + 1 < n ? dp[i_ - 1][j_ + 1] * 2 : 0));
			}
		}
	}
	for (i = 0; i + 1 < n; i++) {
		a = -1;
		for (j = i + 1; j < n; j++)
			if (aa[j] < aa[i]) {
				a = aa[j];
				break;
			}
		for (i_ = i, j1 = i + 1, j2 = n - 1; i_ >= 0; i_--) {
			if (i_ < i && aa[i_] < aa[i_ + 1])
				break;
			k = count(i_, i, aa[i_], aa[i_]);
			while (j1 < n && count(i + 1, j1, aa[i_], aa[i_]) < k)
				j1++;
			k = count(i_, i, 0, aa[i_] - 1);
			while (j2 > i && count(i + 1, j2, 0, aa[i_] - 1) - (a == -1 ? 0 : count(i + 1, j2, a, a)) > k)
				j2--;
			if (j1 <= j2)
				ans = max(ans, (i - i_ + 1) * 2 + (a == -1 ? 0 : count(i + 1, j2, a, a)));
		}
		for (i_ = i, j = i + 1; j < n; j++) {
			if (aa[j] < aa[i]) {
				if (aa[j] != a)
					break;
			} else {
				k = count(i + 1, j, aa[j], aa[j]);
				while (i_ >= 0 && count(i_, i, aa[j], aa[j]) < k) {
					i_--;
					if (i_ < 0 || aa[i_] < aa[i_ + 1]) {
						i_ = -1;
						break;
					}
				}
			}
			if (i_ >= 0 && i - i_ + 1 == j - i - (a == -1 ? 0 : count(i + 1, j, a, a)))
				ans = max(ans, j - i_ + 1 + (i_ > 0 && j + 1 < n ? dp[i_ - 1][j + 1] * 2 : 0));
		}
	}
	return ans;
}

int main() {
	static int aa[N];
	int n, c, i, j, r, tmp, ans;

	scanf("%d%d", &n, &c);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	ans = 0;
	for (r = 0; r < 2; r++) {
		ans = max(ans, solve(aa, n, c));
		for (i = 0, j = n - 1; i < j; i++, j--)
			tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
		for (i = 0; i < n; i++)
			aa[i] = c - 1 - aa[i];
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

aaqqz.c: In function 'main':
aaqqz.c:99:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  scanf("%d%d", &n, &c);
      |  ^~~~~~~~~~~~~~~~~~~~~
aaqqz.c:101:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

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