Submission #140624

#	Time	Username	Problem	Language	Result	Execution time	Memory
140624		MGH	Palinilap (COI16_palinilap)	C++14	100 / 100	114 ms	31356 KiB

palinilap

#include <bits/stdc++.h>
#define  pb push_back
#define  S second
#define  F first
#define ll long long
#define ld long double
using namespace std;
typedef pair<int,int> pii ;
typedef pair<ll,pii> piii ;
//setprecision(8)
//freopen("chip.in","r",stdin);freopen("chip.out","w",stdout);
const ll MOD = 1e9+7;
const ll maxn = 2e5+10 , maxk = 30 , mbn = 727 ;
string s ;
int n ;
ll dpl[maxn] , dpr[maxn] , Ans[maxk+3][maxn]  , pr[2][maxn] , pl[2][maxn] , hl[maxn] , hr[maxn] , pw[maxn] ;
bool check(int i ,int j,int l,int r)
{
	ll A = (hl[j]+MOD-(hl[i-1]*pw[j-i+1])%MOD)%MOD;
	ll B = (hr[l]+MOD-(hr[r+1]*pw[r-l+1])%MOD)%MOD;
	return (A==B) ;
}
int Bs(int l ,int r , int i , int j)
{
	if(i+1==j)
	return i ;
	int mid = (i+j)>>1 ;
	if(check(l-mid,l,r,r+mid))
	return Bs(l,r,mid,j);
	return Bs(l,r,i,mid);
}
int get(int i ,int j)
{
	if((i<=0||j>n)||s[i-1]!=s[j-1])
	return -1 ;
	return Bs(i,j,0,min(i-1,n-j)+1);
}

int main()
{
	ios_base::sync_with_stdio(false);cin.tie();
	cin>>s;
	n = s.size(),pw[0]=1;
	for(int y = 1 ; y <= n ; y++)
	hl[y] = (hl[y-1]*mbn+s[y-1])%MOD ;
	for(int y = n ; y ; y--)
	hr[y] = (hr[y+1]*mbn+s[y-1])%MOD ;
	for(int y = 1 ; y <= n ; y++)
	pw[y] = (mbn*pw[y-1])%MOD ;
	for(int y = 1 ; y <= n ; y++)
	{
		int fa = get(y,y) ;
		pl[1][y]++;pl[1][y+fa+1]--;
		pl[0][y]-=(y-1),pl[0][y+fa+1]+=(y-1),pl[0][y+fa+1]+=fa+1;
		pr[1][y]++,pr[1][y-fa-1]--;
		pr[0][y]-=(n+1-y-1),pr[0][y-fa-1]+=(n+1-y-1),pr[0][y-fa-1]+=fa+1;
		for(int x = 0 ; x < maxk ; x++)
		Ans[x][y]+=fa+1 ;
		if(y-fa==1||y+fa==n)
		continue ;
		int fa2 = get(y-fa-2,y+fa+2)+2;
		Ans[s[y+fa]-'a'+1][y-fa-1]+=fa2;
		Ans[s[y-fa-2]-'a'+1][y+fa+1]+=fa2 ;
	}
	for(int y = 1 ; y < n ;  y++)
	{
		int fa = get(y,y+1) ;
		pl[1][y+1]++,pl[1][y+fa+2]--;
		pl[0][y+1]-=y,pl[0][y+fa+2]+=y,pl[0][y+fa+2]+=fa+1;
		pr[1][y]++,pr[1][y-fa-1]--;
		pr[0][y]-=(n+1-y-1),pr[0][y-fa-1]+=(n+1-y-1),pr[0][y-fa-1]+=fa+1 ;		
		if(y-fa==1||y+1+fa==n)
		continue ;
		int fa2 = get(y-fa-2,y+1+fa+2)+2;
		Ans[s[y+1+fa]-'a'+1][y-fa-1]+=fa2;
		Ans[s[y-fa-2]-'a'+1][y+2+fa]+=fa2;
	}
	for(int y = 1 ; y <= n ; y++)
	pl[0][y]+=pl[0][y-1],pl[1][y]+=pl[1][y-1],dpl[y]=pl[0][y]+1LL*y*pl[1][y] ;
	for(int y = n ; y ; y--)
	pr[0][y]+=pr[0][y+1],pr[1][y]+=pr[1][y+1],dpr[y]=pr[0][y]+1LL*(n+1-y)*pr[1][y];
	ll ans = dpl[n] ;
	for(int y = 1 ; y <= n ; y++)
	for(int k = 0 ; k < maxk ; k++)
	ans = max(ans , 1LL*dpl[y-1]+dpr[y+1]+Ans[k][y]);
	cout<<ans;
	return 0 ;
}

• Subtask 1: 17 / 17
• Subtask 2: 37 / 37
• Subtask 3: 46 / 46