oj.uz

Submission #972085

# Submission time Handle Problem Language Result Execution time Memory
972085 2024-04-30T04:19:21 Z UmairAhmadMirza Palindromes (APIO14_palindrome) C++17
47 / 100
 862 ms 1784 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const mod=1e9+7;
int const base=727;
int const N=1e4+5;
string s;
int n;
int pre[N],suf[N];
int pw[N];
int hash_pre(int l,int r){
	l--;
	return ((pre[r]-((pre[l]*pw[r-l])%mod))+mod)%mod;
}
int hash_suf(int l,int r){
	r++;
	return ((suf[l]-((suf[r]*pw[r-l])%mod))+mod)%mod;
}
void make_hash(){
	pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=(pw[i-1]*base)%mod;
	int hsh=0;
	for (int i = 0; i < n; ++i)
	{
		hsh=(hsh*base)%mod;
		hsh=(hsh+s[i])%mod;
		pre[i+1]=hsh;
	}
	hsh=0;
	for(int i=n-1;i>=0;i--){
		hsh=(hsh*base)%mod;
		hsh=(hsh+s[i]);
		suf[i+1]=hsh;
	}
}
signed main(){
	cin>>s;
	n=s.length();
	make_hash();
	unordered_map<int,int> cnt;
	int h=0;
	for(int l=1;l<=n;l++)
		for(int r=l;r<=n;r++){
			h=hash_pre(l,r);
			if(h==hash_suf(l,r))
				cnt[h]+=(r-l)+1;
		}
	int maxx=0;
	for(auto p:cnt)
		maxx=max(maxx,p.second);
	cout<<maxx<<endl;
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 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 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 356 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 7 ms 344 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 7 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 344 KB Output is correct
11 Correct 3 ms 348 KB Output is correct
12 Correct 3 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 1056 KB Output is correct
2 Correct 411 ms 1108 KB Output is correct
3 Correct 862 ms 1064 KB Output is correct
4 Correct 681 ms 1268 KB Output is correct
5 Correct 250 ms 848 KB Output is correct
6 Correct 271 ms 844 KB Output is correct
7 Correct 297 ms 1000 KB Output is correct
8 Correct 247 ms 604 KB Output is correct
9 Correct 245 ms 692 KB Output is correct
10 Correct 250 ms 848 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1368 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1784 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -