oj.uz

Submission #102453

# Submission time Handle Problem Language Result Execution time Memory
102453 2019-03-25T05:54:27 Z CRE_VIOUS Palindromes (APIO14_palindrome) C++14
0 / 100
 22 ms 5140 KB 
#include <iostream>
#include <cstring>

using namespace std;

const int MAX = 1010;

int memo[MAX][MAX]; // used to store subproblems answers

/**
 *  Return the longest palindromic subsequence
 *  in s[i...j] in a top-down approach.
 *  Time complexity: O(n^2), n = length of s
 */
int lps(const string& s, int i, int j)
{

    // if out of range
    if (i > j)
        return 0;

    // if already computed
    if (memo[i][j] > -1)
        return memo[i][j];

    // if first and last characters are equal
    if (s[i] == s[j])
    {
        // number of equal characters is 2 if i != j, otherwise 1
        int equalCharacters = 2 - (i == j);
        return memo[i][j] = equalCharacters + lps(s, i + 1, j - 1);
    }
    // if characters are not equal, discard either s[i] or s[j]
    return memo[i][j] = max( lps(s, i + 1, j), lps(s, i, j - 1) );
}

// helper function
int longest_palindrome(const string& s)
{

    memset(memo, -1, sizeof memo);
    return lps(s, 0, s.length() - 1);
}

int main()
{

string str;
cin>>str;
    cout << longest_palindrome(str) << '\n';


    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct
2 Incorrect 7 ms 4352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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