Submission #1008989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008989		BF001	Palinilap (COI16_palinilap)	C++17	100 / 100	39 ms	28112 KiB

palinilap

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 100005

int n, md = 1e9 + 7, base = 32, cnt[N], pre[N], f[30][N];
vector<int> pw;
string s, rs;

struct hsh
{
	vector<int> gt;
	hsh(string s){
		int len = (int) s.size();
		while ((int) pw.size() - 1 < len){
			pw.push_back(pw.back() * base % md);
		}
		gt.resize(len + 1, 0);
		for (int i = 1; i <= len; i++){
			gt[i] = (gt[i - 1] * base + s[i - 1] - 'a' + 1) % md;
		}
	}
	int gethsh(int l, int r){
		return (gt[r] - gt[l - 1] * pw[r - l + 1] + md * md) % md;
	}	
};

void ud1(int l, int r){
	if (l > r) return;
	cnt[l] += 1;
	cnt[r + 1] -= 1;
	pre[l] += (1 - l);
	pre[r + 1] -= (1 - l);
}

void ud2(int l, int r){
	if (l > r) return;
	cnt[l] -= 1;
	cnt[r + 1] += 1;
	pre[l] += (r + 1);
	pre[r + 1] -= (r + 1);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
      
    cin >> s;
    rs = s;
    reverse(rs.begin(), rs.end());

    pw.push_back(1);
    hsh h1 = hsh(s);
    hsh h2 = hsh(rs);

    int n = (int) s.size();
    s = " " + s;
    rs = " " + rs;
    int sum = 0;

    for (int i = 1; i <= n; i++){
    	for (int j = i; j <= min(n, i + 1); j++){
    		int l = 1, r = min(i, n - j + 1), rt = 1;
    		if (s[i] == s[j]){
	    		while (l <= r){
	    			int mid = (l + r) >> 1;
	    			int ps = j, ps2 = j + mid - 1;
	    			if (h1.gethsh(i - mid + 1, i) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
	    				rt = mid;
	    				l = mid + 1;
	    			}
	    			else r = mid - 1;
	    		} 
	    		sum += rt;
	    		l = i - rt + 1, r = j + rt - 1;
	    		if (i != j){
	   				ud1(l, i);
	   				ud2(j, r);
	    		}
	    		else {
	    			ud1(l, i - 1);
	    			ud2(i + 1, r);
	    		}
	    	}
    		int ii = l - 1, jj = r + 1;
    		if (s[i] != s[j]) ii = i, jj = j;
    		if (ii < 1 || jj > n) continue;
    		l = 2, r = min(ii, n - jj + 1), rt = 1;
    		while (l <= r){
    			int mid = (l + r) >> 1;
    			int ps = jj  + 1, ps2 = jj + mid - 1;
    			if (h1.gethsh(ii - mid + 1, ii - 1) == h2.gethsh(n - ps2 + 1, n - ps + 1)){
    				rt = mid;
    				l = mid + 1;
    			}
    			else r = mid - 1;
    		}
    		f[s[ii] - 'a' + 1][jj] += rt;
    		f[s[jj] - 'a' + 1][ii] += rt;
    	}
    }

    int res = sum;

    for (int i = 1; i <= n; i++){
    	pre[i] += pre[i - 1];
    	cnt[i] += cnt[i - 1];
    	for (int j = 1; j <= 26; j++){
    		res = max(res , sum - (i * cnt[i] + pre[i]) + f[j][i]);
    	}
    }

    cout << res;

    return 0;
}     

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