oj.uz

Submission #40071

# Submission time Handle Problem Language Result Execution time Memory
40071 2018-01-26T11:20:03 Z 5ak0 Palinilap (COI16_palinilap) C++14
17 / 100
 1000 ms 123964 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;

const int N = 300000;

string s;
int ans;

int calc(string str){
    int n = str.size();
    int dp[n][n];
    memset(dp, 0, sizeof(dp));
    bool P[n][n];
    memset(P, false , sizeof(P));
    for (int i= 0; i< n; i++)
        P[i][i] = true;
    for (int i=0; i<n-1; i++)
    {
        if (str[i] == str[i+1])
        {
            P[i][i+1] = true;
            dp[i][i+1] = 1 ;
        }
    }
    for (int gap=2 ; gap<n; gap++){
        for (int i=0; i<n-gap; i++){
            int j = gap + i;
            if (str[i] == str[j] && P[i+1][j-1] )
                P[i][j] = true;
            if (P[i][j] == true)
                dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1 - dp[i+1][j-1];
            else
                dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
        }
    }
    return dp[0][n-1] + n;
}

int main(){
    cin >> s;
    ans = calc(s);
    for (int i = 0; i < s.size(); ++i){
        char ch = s[i];
        for (char j = 'a'; j <= 'z'; ++j){
            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:57: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 42 ms 2020 KB Output is correct
2 Correct 63 ms 2020 KB Output is correct
3 Correct 66 ms 2020 KB Output is correct
4 Correct 78 ms 2020 KB Output is correct
5 Correct 62 ms 2020 KB Output is correct

Subtask #2
0 / 37.0

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

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -