oj.uz

Submission #1026468

# Submission time Handle Problem Language Result Execution time Memory
1026468 2024-07-18T06:32:31 Z Muhammet Palinilap (COI16_palinilap) C++17
54 / 100
 79 ms 197236 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 = 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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 97148 KB Output is correct
2 Correct 30 ms 97104 KB Output is correct
3 Correct 11 ms 97116 KB Output is correct
4 Correct 6 ms 60020 KB Output is correct
5 Correct 8 ms 82524 KB Output is correct
6 Correct 9 ms 97136 KB Output is correct
7 Correct 10 ms 97116 KB Output is correct

Subtask #3
0 / 46.0

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