Submission #972088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972088	2024-04-30T04:36:43 Z	MuhammadSaram	Palindromes (APIO14_palindrome)	C++17	23 / 100	77 ms	131072 KB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int h=71, mod = 1e9 + 7;

signed main()
{
	string s;
	cin>>s;
	int n=s.size();
	int ha[n][n];
	bool dp[n][n];
	int ans=0;
	int cn[26]={},ct[26]={};
	for (int i=0;i<n;i++)
	{
		int x=0;
		for (int j=i;j<n;j++)
		{
			x*=h,x+=s[j],x%=mod;
			ha[i][j]=x;
		}
		dp[i][i]=1;
		ans=max(ans,++cn[s[i]-'a']);
		if (i)
			dp[i-1][i]=(s[i-1]==s[i]);
		if (i and dp[i-1][i])
			ans=max(ans,(++ct[s[i-1]-'a'])*2);
	}
	for (int len=2;len<n;len++)
	{
		unordered_map<int,int> cnt;
		for (int i=0;i+len<n;i++)
		{
			int j=i+len;
			dp[i][j]=dp[i+1][j-1]&(s[i]==s[j]);
			if (dp[i][j])
				ans=max(ans,(len+1)*(++cnt[ha[i][j]]));
		}
	}
	cout<<ans<<endl;
	
	return 0;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	352 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	352 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	352 KB	Output is correct
8	Correct	1 ms	344 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	436 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	432 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	1 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	344 KB	Output is correct
27	Correct	0 ms	344 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	1 ms	348 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	9052 KB	Output is correct
2	Correct	9 ms	9048 KB	Output is correct
3	Correct	14 ms	9052 KB	Output is correct
4	Correct	9 ms	9052 KB	Output is correct
5	Correct	14 ms	9052 KB	Output is correct
6	Correct	13 ms	9004 KB	Output is correct
7	Correct	9 ms	9052 KB	Output is correct
8	Correct	12 ms	9136 KB	Output is correct
9	Correct	9 ms	9248 KB	Output is correct
10	Correct	10 ms	9120 KB	Output is correct
11	Correct	8 ms	9048 KB	Output is correct
12	Correct	9 ms	9052 KB	Output is correct

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	77 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	69 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	74 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-