oj.uz

Submission #666431

# Submission time Handle Problem Language Result Execution time Memory
666431 2022-11-28T15:49:34 Z Felicity Palinilap (COI16_palinilap) C++14
17 / 100
 1000 ms 720 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=5e3+5;
const ll mo=1e9+7;
int dp[5005][5005],n,dp1[5005][5005];
string ss,t;
const int maxn = 5005;
char str[maxn];
char s[maxn*2];
int p[maxn*2];
int len;
ll Manacher(){
    int i;
    s[0] = '$';
    s[1] = '#';
    len = strlen(str);
    //define s from str
    for(i=0; i<len; i++) {
        s[i*2 +2] = str[i];
        s[i*2 +3] = '#';
    }
    len = i*2+2;
    s[len] = '\0';
    int MaxL, id = 0;
    MaxL =0;

    memset(p,0,sizeof(p));

    for(int i=0; i<len; i++) {
        if(p[id] + id > i)
            p[i] = min(p[2*id-i], p[id] + id -i);
        else
            p[i] = 1;
        while(s[i+p[i]] == s[i-p[i]])
            p[i]++;
        if(p[i] + i > p[id]+id) {
            id = i;
        }
        MaxL += p[i]/2;
    }
    return MaxL;
}
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];
}
char a[N], b[2 * N];
void solve(){

        ll res=0;
        cin>>str;
        f(i,0,strlen(str)-1){
            a[i]=str[i];
        }
        f(i,1,strlen(str)){
            f(j,0,strlen(a)-1){
                str[j]=a[j];
            }
            f(j,1,26){
                str[i-1]=char(j+'a'-1);
                res=max(res,Manacher());
            }
        }
        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
*/

Compilation message

palinilap.cpp: In function 'void solve()':
palinilap.cpp:4:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define f(i,a,b) for(ll i=a;i<=b;++i)
......
   76 |         f(i,0,strlen(str)-1){
      |           ~~~~~~~~~~~~~~~~~   
palinilap.cpp:76:9: note: in expansion of macro 'f'
   76 |         f(i,0,strlen(str)-1){
      |         ^
palinilap.cpp:4:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define f(i,a,b) for(ll i=a;i<=b;++i)
......
   79 |         f(i,1,strlen(str)){
      |           ~~~~~~~~~~~~~~~     
palinilap.cpp:79:9: note: in expansion of macro 'f'
   79 |         f(i,1,strlen(str)){
      |         ^
palinilap.cpp:4:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define f(i,a,b) for(ll i=a;i<=b;++i)
......
   80 |             f(j,0,strlen(a)-1){
      |               ~~~~~~~~~~~~~~~ 
palinilap.cpp:80:13: note: in expansion of macro 'f'
   80 |             f(j,0,strlen(a)-1){
      |             ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 8 ms 380 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 5 ms 340 KB Output is correct

Subtask #2
0 / 37.0

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

Subtask #3
0 / 46.0

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