oj.uz

Submission #40074

# Submission time Handle Problem Language Result Execution time Memory
40074 2018-01-26T11:44:21 Z 5ak0 Palinilap (COI16_palinilap) C++14
17 / 100
 1000 ms 3112 KB 
/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7, MAXN = 1e5 + 10;

string s;
int ans;
int d[MAXN], d2[MAXN];

int calc(string c){
    int n = c.size();
    int l, r;
    l = r = -1;
    for (int i = 0; i < n; ++i){
        d[i] = 1;
        if (i <= r)
            d[i] = min(r - i + 1, d[l + (r - i)]);
        while (i + d[i] < n && i - d[i] >= 0 && c[i - d[i]] == c[i + d[i]])
            d[i]++;
        if (i + d[i] - 1 > r)
            l = i - d[i] + 1, r = i + d[i] - 1;
    }
    l = r = -1;
    for (int i = 0; i < n; ++i){
        d2[i] = 0;
        if (i <= r)
            d2[i] = min(r - i, d2[l + (r - i) - 1]);
        while (i + d2[i] + 1 < n && i - d2[i] >= 0 && c[i - d2[i]] == c[i + d2[i] + 1])
            ++d2[i];
        if (i + d2[i] > r)
            l = i - d2[i] + 1, r = i + d2[i];
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i){
        ans += (d[i] - 1);
        ans += d2[i];
    }
    return ans + c.size();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin >> s;
    ans = calc(s);
    for (int i = 0; i < s.size(); ++i){
        char ch = s[i];
        for (char j = 'a'; j <= 'z'; ++j){
            if (j == ch)
                continue;
            s[i] = j;
            ans = max(ans, calc(s));
        }
        s[i] = ch;
    }
    cout << ans;
    return 0;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i){
                       ^

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2960 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 3112 KB Execution timed out
2 Halted 0 ms 0 KB -