oj.uz

답안 #486533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
486533 2021-11-11T22:29:32 Z rainboy Palinilap (COI16_palinilap) C
54 / 100
 1000 ms 24184 KB 
#include <stdio.h>
#include <string.h>

#define N	300000
#define A	26

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

void manacher(char *cc, int *rr, int n) {
	static char cc_[N * 2 + 1];
	static int rr_[N * 2];
	int i, o, x;

	for (i = 0; i < n * 2 + 1; i++)
		cc_[i] = i % 2 == 1 ? cc[i / 2] : ' ';
	for (i = 0, o = 0, x = 0; i < n * 2 + 1; i++)
		if (i + rr_[o + o - i] < x)
			rr_[i] = rr_[o + o - i];
		else {
			o = i, x = max(x, i);
			while (x >= 0 && x < n * 2 + 1 && cc_[x] == cc_[o + o - x])
				x++;
			rr_[i] = x - o;
		}
	for (i = 0; i <= n - 1 + n - 1; i++)
		rr[i] = rr_[i + 1] / 2;
}

int main() {
	static long long kk[N][A], ll[N], mm[N];
	static int rr[N];
	static char cc[N + 1];
	int n, h, i, i_, j, j_, ij, a;
	long long k_;

	scanf("%s", cc), n = strlen(cc);
	manacher(cc, rr, n);
	for (ij = 0; ij <= n - 1 + n - 1; ij++) {
		h = ij / 2, i_ = h - rr[ij], j_ = ij - i_;
		if (ij % 2 == 0) {
			ll[h] += h - i_, ll[h + 1] -= (h - i_) * 2, ll[h + 2] += h - i_;
			mm[h] -= h - i_, mm[h + 1] += (h - i_) * 2, mm[h + 2] -= h - i_;
		}
		ll[0] += h - i_, ll[1] -= h - i_;
		ll[i_ + 1]--, ll[h + 1]++, ll[ij - h + 1]++, ll[j_ + 1]--;
		mm[i_ + 1]++, mm[h + 1]--, mm[ij - h + 1]--, mm[j_ + 1]++;
		for (i = i_, j = j_; i >= 0 && j < n; i--, j++) {
			if (i < i_ && cc[i] != cc[j])
				break;
			kk[i_][cc[j_] - 'a']++, kk[j_][cc[i_] - 'a']++;
		}
	}
	for (i = 1; i < n; i++)
		ll[i] += ll[i - 1];
	for (i = 1; i < n; i++)
		ll[i] += ll[i - 1];
	for (i = 1; i < n; i++)
		mm[i] += mm[i - 1];
	for (i = 1; i < n; i++)
		mm[i] += mm[i - 1];
	k_ = 0;
	for (i = 0; i < n; i++)
		for (a = 0; a < A; a++)
			k_ = max(k_, kk[i][a] + ll[i] + (cc[i] == a + 'a' ? mm[i] : 0));
	printf("%lld\n", k_);
	return 0;
}

Compilation message

palinilap.c: In function 'main':
palinilap.c:36:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 1228 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct

Subtask #3
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 24012 KB Output is correct
2 Correct 17 ms 24080 KB Output is correct
3 Correct 16 ms 24140 KB Output is correct
4 Correct 23 ms 24184 KB Output is correct
5 Correct 19 ms 24132 KB Output is correct
6 Correct 22 ms 24092 KB Output is correct
7 Correct 18 ms 24180 KB Output is correct
8 Correct 10 ms 3852 KB Output is correct
9 Correct 18 ms 24140 KB Output is correct
10 Correct 19 ms 24140 KB Output is correct
11 Correct 19 ms 24180 KB Output is correct
12 Correct 17 ms 24140 KB Output is correct
13 Correct 23 ms 24140 KB Output is correct
14 Correct 18 ms 24140 KB Output is correct
15 Correct 18 ms 24132 KB Output is correct
16 Execution timed out 1081 ms 13132 KB Time limit exceeded
17 Halted 0 ms 0 KB -