oj.uz

Submission #486534

# Submission time Handle Problem Language Result Execution time Memory
486534 2021-11-11T22:30:25 Z rainboy Palinilap (COI16_palinilap) C
54 / 100
 1000 ms 24056 KB 
#include <stdio.h>
#include <string.h>

#define N	100100
#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 * 2];
	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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24012 KB Output is correct
2 Correct 17 ms 23948 KB Output is correct
3 Correct 17 ms 24048 KB Output is correct
4 Correct 20 ms 23932 KB Output is correct
5 Correct 18 ms 23980 KB Output is correct
6 Correct 17 ms 23988 KB Output is correct
7 Correct 20 ms 24020 KB Output is correct
8 Correct 12 ms 3728 KB Output is correct
9 Correct 18 ms 23952 KB Output is correct
10 Correct 18 ms 24012 KB Output is correct
11 Correct 18 ms 24012 KB Output is correct
12 Correct 17 ms 24056 KB Output is correct
13 Correct 19 ms 24036 KB Output is correct
14 Correct 17 ms 24012 KB Output is correct
15 Correct 18 ms 24052 KB Output is correct
16 Execution timed out 1090 ms 13084 KB Time limit exceeded
17 Halted 0 ms 0 KB -