Submission #1026468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026468		Muhammet	Palinilap (COI16_palinilap)	C++17	54 / 100	79 ms	197236 KiB

palinilap

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

#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

const ll N = 5005;
const ll M = 1e9 + 7;

int a[N][N], b[N];

int f(char c){
	return (c-'a');
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	string s;
	cin >> s;

	int n = sz(s), ans = 0;
	for(int i = 0; i < n; i++){
		int l = i, r = i, l1 = -1, r1 = n;
		bool tr = 0;
		while(l >= 0 and r < n){
			if(s[l] == s[r]){
				if(tr == 0){
					ans++;
				}
				else {
					a[l1][f(s[r1])]++;
					a[r1][f(s[l1])]++;
				}
			}
			else {
				if(tr == 1) break;
				tr = 1;
				l1 = l, r1 = r;
				a[l][f(s[r])]++;
				a[r][f(s[l])]++;
			}
			l--;
			r++;
			if(tr == 0){
				l1 = l, r1 = r;
			}
		}
		int l2 = l1+1, r2 = r1-1;
		while(l2 < i){
			b[l2] += abs(l2-l1);
			b[r2] += abs(r1-r2);
			l2++;
			r2--;
		}
	}

	for(int i = 0; i < n-1; i++){
		int l = i, r = i+1, l1 = -1, r1 = n;
		bool tr = 0;
		while(l >= 0 and r < n){
			if(s[l] == s[r]){
				if(tr == 0){
					ans++;
				}
				else {
					a[l1][f(s[r1])]++;
					a[r1][f(s[l1])]++;
				}
			}
			else {
				if(tr == 1) break;
				tr = 1;
				l1 = l, r1 = r;
				a[l][f(s[r])]++;
				a[r][f(s[l])]++;
			}
			l--;
			r++;
			if(tr == 0){
				l1 = l, r1 = r;
			}
		}
		int l2 = l1+1, r2 = r1-1;
		while(l2 <= i){
			b[l2] += abs(l2-l1);
			b[r2] += abs(r1-r2);
			l2++;
			r2--;
		}
	}

	int mx = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < 26; j++){
			mx = max(mx,a[i][j]-b[i]);
		}
	}

	cout << ans + mx;

	return 0;
}

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