Submission #1351515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351515		hashimzaderashid	Palinilap (COI16_palinilap)	C++20	17 / 100	1095 ms	589824 KiB

palinilap

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ll t,a,b,c,d,e,f,g;
    string s;
    cin>>s;
    s = " "+s;
    a = s.size()-1;
    string sk = s;
    ll ans = 0;
    for(int k = 1;k<=a;k++){
        for(char x = 'a';x<='z';x++){
            s = sk;
            s[k] = x;
            vector<vector<bool>>dp(a+1,vector<bool>(a+1,0));
            ll say = 0;
            for(int i = a;i>=1;i--){
                for(int j = 1;j<=a;j++){
                    if(j < i){
                        continue;
                    }
                    if(j == i){
                        dp[i][i] = 1;
                        say++;
                        continue;
                    }
                    if(i+1 == j){
                        if(s[i] == s[j]){
                            dp[i][j] = 1;
                            say++;
                        }
                        continue;
                    }
                    if(s[i] == s[j] and dp[i+1][j-1]){
                        dp[i][j] = 1;
                        say++;
                    }
                }
            }
            ans = max(ans,say);
        }
    }
    cout<<ans<<endl;
}
//By Rashid_Hashimzade

• Subtask 1: 17 / 17
• Subtask 2: 0 / 37
• Subtask 3: 0 / 46