Submission #666415

#	Time	Username	Problem	Language	Result	Execution time	Memory
666415		Felicity	Palinilap (COI16_palinilap)	C++14	17 / 100	1103 ms	524288 KiB

palinilap

#include<bits/stdc++.h>
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;++i)
#define ar array
#define pb push_back
#define e0 exit(0)
#define ConVitKeu QuacQuac
using namespace std;
const int N=3e5+1;
const ll mo=1e9+7;
ll dp[5005][5005],n,dp1[5005][5005];
string s,t;
ll tinh(string s){
    f(i,1,n)f(j,1,n)dp[i][j]=0,dp1[i][j]=0;
    f(i,1,n){
        f(j,1,i){
            if(i==j)dp[j][i]=1;
            else{
                if(s[i]==s[j]){
                    if(i==j+1)dp[j][i]=1;
                    else dp[j][i]=dp[j+1][i-1];
                }
            }
        }
    }
    f(i,1,n){
        f(j,1,n){
            dp1[i][j]=dp1[i-1][j]+dp1[i][j-1]+dp[i][j]-dp1[i-1][j-1];
        }
    }
    ll l=1,r=n;
    return dp1[r][r]-dp1[r][l-1]-dp1[l-1][r]+dp1[l-1][l-1];
}
void solve(){
    cin>>s;
    n=s.size();
    s=' '+s;
    ll res=0;
    f(i,1,n){
        t=s;
        f(j,1,26){
            t[i]=char(j+'a'-1);
            res=max(res,tinh(t));
        }
    }
    cout<<res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("DEBT.INP","r",stdin);
    //freopen("DEBT.OUT","w",stdout);
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
/*
6
3 2 1 5 2 4
1 3
2 4
1 5
2 1
3 6
*/

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