Submission #625401

#	Time	Username	Problem	Language	Result	Execution time	Memory
625401		NintsiChkhaidze	Palinilap (COI16_palinilap)	C++14	100 / 100	268 ms	40412 KiB

palinilap

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define s second
#define f first
using namespace std;

const int N = 100005;
int mod = 1000000007,PR = 31,n,h[N],p[N],add[N][30],dlt[N],Rp[N],Rh[N],a1[N],b1[N];
int st[N],Rst[N];
vector <int> en[N],Ren[N];
string s;

bool check(int l1,int r1,int l2,int r2){
    long long val1 = h[r1];
    if (l1) val1 -= h[l1 - 1];
    val1 = (val1%mod+mod)%mod;
    
    long long val2 = Rh[l2];
    if (r2 < n - 1) val2 -= Rh[r2 + 1];
    val2 = (val2%mod+mod)%mod;
    
    return ((val1 * Rp[r2])%mod == (val2 * p[l1])%mod);
}

int get(int L,int R){
    int res=0,l = 0,r = n;
    while (l <= r){
        int mid = (l + r)>>1;
        if (L - mid + 1 >= 0 && R + mid - 1 < n && check(L - mid + 1,L,R,R + mid - 1)) 
            res = mid, l = mid + 1;
        else 
            r = mid - 1;
    }
    return res;
}
signed main (){
    cin>>s;
    n = s.size();
    for (int i = 0; i < n; i++){
        if (i == 0){
            p[i] = 1;
            h[i] = (s[i] - 'a' + 1)%mod;
        }else{
            p[i] = (p[i - 1] * PR)%mod;
            h[i] = (h[i - 1] + (p[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    for (int i = n - 1; i >= 0; i--){
        if (i == n - 1){
            Rp[i] = 1;
            Rh[i] = (s[i] - 'a' + 1)%mod;
        }else{
            Rp[i] = (Rp[i + 1] * PR)%mod;
            Rh[i] = (Rh[i + 1] + (Rp[i] * (s[i] - 'a' + 1))%mod)%mod;
        }
    }
    
    int base_ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = i; j <= min(n - 1,i + 1); j++){
            int len = get(i,j);
            base_ans += len;
            int l = i - len + 1,r = j + len - 1;
            if (i != j){
                if (i - len + 1 <= i){
                    st[i - len + 1]++;
                    en[i].pb(len);
                }
                
                if (j + len - 1 >= j){
                    Rst[j+len-1]++;
                    Ren[j].pb(len);
                }
            }else{
                if (i - len + 1 <= i - 1){
                    st[i - len + 1]++;
                    en[i-1].pb(len - 1);
                }
                
                if (j + len - 1 >= i + 1){
                    Rst[j+len-1]++;
                    Ren[i+1].pb(len - 1);
                }
            }
            
            if (l > 0 && r < n - 1){
                l--,r++;
                int val = get(l - 1,r + 1) + 1;
                add[l][s[r] - 'a' + 1] += val;
                add[r][s[l] - 'a' + 1] += val;
            }
        }
    }
    int sm=0,cnt=0;
    for (int i = 0; i < n; i++){
        cnt += st[i];
        sm += cnt;
        dlt[i] = -sm;
        
        for (int x: en[i]){
            cnt--;
            sm -= x;
        }
    }
    
    sm=0,cnt=0;
    for (int i= n-1;i>=0;i--){
        cnt += Rst[i];
        sm += cnt;
        dlt[i] += -sm;
        for (int x: Ren[i]){
            cnt--;
            sm -= x;
        }
    }
    
    int best_add=0,sum = 0;
    for (int i = 0; i < n; i++){
        for (int j = 1; j <= 26; j++){
            if (j == s[i] - 'a' + 1) continue;
            if (add[i][j] + dlt[i] > best_add)
                best_add = add[i][j] + dlt[i];  
        }
    }
    cout<<best_add + base_ans;
}

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:119:20: warning: unused variable 'sum' [-Wunused-variable]
  119 |     int best_add=0,sum = 0;
      |                    ^~~

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