Submission #1196937

#TimeUsernameProblemLanguageResultExecution timeMemory
1196937MalixPalindromes (APIO14_palindrome)C++20
0 / 100
74 ms196608 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,ll,ll> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; struct node{ int sz; int next[26]; int suf; }; int n,pos=2,cnt[300002]; string s; vector<node> a(3000002); int suff=0; void letter(int x){ int c=s[x]-'a'; if(a[suff].sz==x)suff=a[suff].suf; while(suff>0&&s[x-1-a[suff].sz]!=s[x])suff=a[suff].suf; if(a[suff].next[c]==-1){ a[suff].next[c]=pos; a[pos].sz=a[suff].sz+2; while(suff>0&&s[x-1-a[suff].sz]!=s[x])suff=a[suff].suf; a[pos].suf=suff; if(a[pos].sz==1)a[pos].suf=1; cnt[pos]++; suff=pos; pos++; } else cnt[a[suff].next[c]]++; } int main() { // ios::sync_with_stdio(0); // cin.tie(0); cin>>s; n=s.size(); memset(cnt,0,sizeof(cnt)); REP(i,0,n+2)REP(j,0,26)a[i].next[j]=-1; a[0].sz=-1;a[0].suf=0; a[1].sz=0;a[1].suf=0; REP(i,0,n)letter(i); priority_queue<pi> pq; REP(i,2,n+2)pq.push({a[i].sz,i}); int ans=0; REP(i,0,n){ int x=pq.top().S; ans=max(ans,a[x].sz*cnt[x]); REP(j,0,26)if(a[x].next[j]!=-1)cnt[a[x].next[j]]+=cnt[x]; pq.pop(); } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...