oj.uz

Submission #1026458

# Submission time Handle Problem Language Result Execution time Memory
1026458 2024-07-18T06:19:08 Z Muhammet Palinilap (COI16_palinilap) C++17
0 / 100
 80 ms 197220 KB 
#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;
		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(l1 != -1){
			int l2 = l1+1, r2 = r1-1;
			while(l2 < i){
				b[l2] += (l2-l1)-1;
				b[r2] += (r1-r2)-1;
				l2++;
				r2--;
			}
		}
	}

	for(int i = 0; i < n-1; i++){
		int l = i, r = i+1, l1 = -1, r1;
		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(l1 != -1){
			int l2 = l1+1, r2 = r1-1;
			while(l2 < i){
				b[l2] += (l2-l1)-1;
				b[r2] += (r1-r2)-1;
				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]*(j != f(s[i])));
		}
	}

	cout << ans + mx;

	return 0;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 97196 KB Output is correct
2 Incorrect 25 ms 97116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 197220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -