oj.uz

Submission #486536

# Submission time Handle Problem Language Result Execution time Memory
486536 2021-11-11T22:32:31 Z rainboy Palinilap (COI16_palinilap) C
54 / 100
 1000 ms 24064 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]++;
		if (i_ < 0 || j_ >= n)
			continue;
		i = i_, j = j_;
		while (i >= 0 && j < n && (i == i_ || cc[i] == cc[j]))
			i--, j++;
		kk[i_][cc[j_] - 'a'] += i_ - i, kk[j_][cc[i_] - 'a'] += j - j_;
	}
	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 0 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 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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24060 KB Output is correct
2 Correct 17 ms 23988 KB Output is correct
3 Correct 16 ms 24060 KB Output is correct
4 Correct 19 ms 23960 KB Output is correct
5 Correct 19 ms 24060 KB Output is correct
6 Correct 19 ms 24064 KB Output is correct
7 Correct 20 ms 24060 KB Output is correct
8 Correct 10 ms 3644 KB Output is correct
9 Correct 19 ms 24016 KB Output is correct
10 Correct 21 ms 23956 KB Output is correct
11 Correct 19 ms 24052 KB Output is correct
12 Correct 17 ms 24060 KB Output is correct
13 Correct 22 ms 24056 KB Output is correct
14 Correct 18 ms 24064 KB Output is correct
15 Correct 17 ms 23956 KB Output is correct
16 Execution timed out 1084 ms 14420 KB Time limit exceeded
17 Halted 0 ms 0 KB -