oj.uz

Submission #103337

# Submission time Handle Problem Language Result Execution time Memory
103337 2019-03-29T18:47:10 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
0 / 100
 73 ms 34944 KB 
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 3e5 + 5, A = 26;
int to[N][A], link[N], len[N], w[N];
string s;
int n, z = 2, suf;

void addLetter(int p) {
	while (p - len[suf] - 1 < 0 || s[p - len[suf] - 1] != s[p])
		suf = link[suf];

	int c = s[p] - 'a';
	if (to[suf][c] != -1) {
		suf = to[suf][c];
		w[to[suf][c]]++;
		return;
	}

	
	to[suf][c] = z;
	w[z]++;
	len[z] = len[suf] + 2;

	if (len[z] == 1) {
		link[z] = 0;
	}
	else {
		int v = link[suf];
		while (p - len[v] - 1 < 0 || s[p - len[v] - 1] != s[p])
			v = link[v];

		link[z] = to[v][c];
	}

	suf = z;
	z++;
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;
	n = s.size();

	memset(to, -1, sizeof(to));

	len[0] = 0;
	len[1] = -1;
	link[0] = 1;
	link[1] = 1;

	suf = 0;

	for (int i = 0; i < n; i++) {
		addLetter(i);
	}

	for (int i = z - 1; i >= 0; i--) {
		w[link[i]] += w[i];
	}

	ll ans = 0;

	for (int i = 0; i < z; i++) {
		ans = max(ans, len[i] * (ll)w[i]);
	}

	cout << ans;

	return 0;
}

Compilation message

palindrome.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 30848 KB Output is correct
2 Correct 26 ms 30820 KB Output is correct
3 Correct 25 ms 30880 KB Output is correct
4 Correct 27 ms 30848 KB Output is correct
5 Correct 24 ms 30848 KB Output is correct
6 Correct 26 ms 30840 KB Output is correct
7 Correct 28 ms 30840 KB Output is correct
8 Correct 26 ms 30840 KB Output is correct
9 Correct 24 ms 30828 KB Output is correct
10 Correct 27 ms 30848 KB Output is correct
11 Correct 24 ms 30848 KB Output is correct
12 Correct 25 ms 30848 KB Output is correct
13 Correct 26 ms 30848 KB Output is correct
14 Correct 27 ms 30908 KB Output is correct
15 Correct 29 ms 30840 KB Output is correct
16 Correct 24 ms 30840 KB Output is correct
17 Correct 29 ms 30900 KB Output is correct
18 Incorrect 24 ms 30876 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30976 KB Output is correct
2 Correct 23 ms 30976 KB Output is correct
3 Correct 23 ms 30848 KB Output is correct
4 Correct 27 ms 30840 KB Output is correct
5 Correct 25 ms 30840 KB Output is correct
6 Correct 30 ms 30968 KB Output is correct
7 Correct 28 ms 30968 KB Output is correct
8 Correct 28 ms 30864 KB Output is correct
9 Correct 25 ms 30928 KB Output is correct
10 Incorrect 26 ms 30968 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 30976 KB Output is correct
2 Correct 28 ms 31068 KB Output is correct
3 Correct 25 ms 31016 KB Output is correct
4 Correct 26 ms 31100 KB Output is correct
5 Correct 31 ms 30968 KB Output is correct
6 Correct 29 ms 31100 KB Output is correct
7 Correct 28 ms 30968 KB Output is correct
8 Incorrect 34 ms 30936 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 32248 KB Output is correct
2 Correct 73 ms 32248 KB Output is correct
3 Correct 27 ms 32248 KB Output is correct
4 Correct 29 ms 32220 KB Output is correct
5 Correct 31 ms 32248 KB Output is correct
6 Correct 31 ms 32000 KB Output is correct
7 Correct 28 ms 32120 KB Output is correct
8 Incorrect 28 ms 31088 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34836 KB Output is correct
2 Correct 40 ms 34816 KB Output is correct
3 Correct 46 ms 34944 KB Output is correct
4 Correct 38 ms 34944 KB Output is correct
5 Correct 44 ms 34876 KB Output is correct
6 Correct 53 ms 34492 KB Output is correct
7 Correct 39 ms 34308 KB Output is correct
8 Incorrect 36 ms 31404 KB Output isn't correct
9 Halted 0 ms 0 KB -