oj.uz

Submission #103335

# Submission time Handle Problem Language Result Execution time Memory
103335 2019-03-29T18:46:28 Z Minnakhmetov Palindromes (APIO14_palindrome) C++14
0 / 100
 47 ms 34864 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) {
		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 29 ms 30812 KB Output is correct
2 Correct 33 ms 30896 KB Output is correct
3 Correct 28 ms 30872 KB Output is correct
4 Correct 34 ms 30900 KB Output is correct
5 Correct 36 ms 30840 KB Output is correct
6 Correct 45 ms 30840 KB Output is correct
7 Correct 27 ms 30868 KB Output is correct
8 Correct 26 ms 30840 KB Output is correct
9 Correct 28 ms 30840 KB Output is correct
10 Correct 31 ms 30828 KB Output is correct
11 Incorrect 26 ms 30896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30904 KB Output is correct
2 Correct 28 ms 30940 KB Output is correct
3 Correct 29 ms 30936 KB Output is correct
4 Correct 28 ms 30892 KB Output is correct
5 Correct 28 ms 30940 KB Output is correct
6 Correct 23 ms 30968 KB Output is correct
7 Correct 28 ms 30840 KB Output is correct
8 Correct 27 ms 30948 KB Output is correct
9 Correct 28 ms 30848 KB Output is correct
10 Correct 25 ms 30896 KB Output is correct
11 Correct 25 ms 30840 KB Output is correct
12 Incorrect 28 ms 30800 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30968 KB Output is correct
2 Correct 25 ms 30968 KB Output is correct
3 Correct 28 ms 31024 KB Output is correct
4 Correct 30 ms 31056 KB Output is correct
5 Correct 25 ms 31068 KB Output is correct
6 Incorrect 29 ms 31004 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 32300 KB Output is correct
2 Correct 28 ms 32248 KB Output is correct
3 Correct 30 ms 32308 KB Output is correct
4 Correct 29 ms 32248 KB Output is correct
5 Correct 36 ms 32304 KB Output is correct
6 Correct 30 ms 31828 KB Output is correct
7 Correct 28 ms 32036 KB Output is correct
8 Correct 26 ms 31136 KB Output is correct
9 Incorrect 24 ms 31140 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 34864 KB Output is correct
2 Incorrect 38 ms 33496 KB Output isn't correct
3 Halted 0 ms 0 KB -