oj.uz

Submission #990732

# Submission time Handle Problem Language Result Execution time Memory
990732 2024-05-31T06:41:22 Z vjudge1 Palinilap (COI16_palinilap) C++17
17 / 100
 1000 ms 5016 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=2e5+5;
int const mod=1e9+7;
vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}

int main(){
	string s;
	cin>>s;
	vector<int> v=manacher(s);
	long long ans=0;
	for(int i=0;i<s.length();i++){
		char o=s[i];
		for(int j=0;j<26;j++){
			s[i]='a'+j;
			v=manacher(s);
			long long tans=0; 
			for(auto i:v)
				tans+=i/2;
			ans=max(ans,tans);
		}
		s[i]=o;
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<s.length();i++){
      |              ~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 7 ms 440 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 6 ms 348 KB Output is correct
5 Correct 6 ms 348 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 5016 KB Time limit exceeded
2 Halted 0 ms 0 KB -