oj.uz

Submission #666416

# Submission time Handle Problem Language Result Execution time Memory
666416 2022-11-28T15:10:25 Z Felicity Palinilap (COI16_palinilap) C++14
17 / 100
 1000 ms 398536 KB 
#pragma GCC optimize("O2")
#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;
int 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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 980 KB Output is correct
2 Correct 111 ms 1204 KB Output is correct
3 Correct 110 ms 1204 KB Output is correct
4 Correct 109 ms 1108 KB Output is correct
5 Correct 108 ms 1220 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 196200 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 46.0

# Verdict Execution time Memory Grader output
1 Runtime error 316 ms 398536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -