Submission #1008968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008968		BF001	Palinilap (COI16_palinilap)	C++17	0 / 100	34 ms	18776 KiB

palinilap

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

#define int long long
#define N 100005

int n, md = 1e9 + 7, base = 32, 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;
	}	
};

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){
	   				pre[l] += 1;
	    			pre[r + 1] += -1;
	    		}
	    		else {
	    			pre[l] ++;
	    			pre[i]--;
	    			pre[i + 1]++;
	    			pre[r + 1]--;
	    		}
	    	}
    		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];
    	for (int j = 1; j <= 26; j++){
    		res = max(res , sum - pre[i] + f[j][i]);
    	}
    }

    cout << res;

    return 0;
}     

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