Submission #554669

#	Time	Username	Problem	Language	Result	Execution time	Memory
554669		MrDeboo	Palindromes (APIO14_palindrome)	C++17	8 / 100	1086 ms	51544 KiB

palindrome

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<int MOD>
struct ModInt {
    unsigned x;
    ModInt() : x(0) { }
    ModInt(signed sig) : x(sig%MOD) {  }
    ModInt(signed long long sig) : x(sig%MOD) { }
    int get() const { return (int)x; }
    ModInt pow(long long p) { ModInt res = 1, a = *this; while (p) { if (p & 1) res *= a; a *= a; p >>= 1; } return res; }

    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return (*this) *= that.pow(MOD - 2); }

    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    bool operator<(ModInt that) const { return x < that.x; }
    friend ostream& operator<<(ostream &os, ModInt a) { os << a.x; return os; }
};

#define endl '\n'
#define mod 1000000007
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef long long ll;
typedef long double ld;
typedef ModInt<mod> mint;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;


string FileS="";
bool tstc=0;
void dothethingythatfindsthesolutiontotheproblem(){
    string s;
    cin>>s;
    map<deque<char>,ll>mp;
    ll ans=0;
    for(int i=0;i<sz(s);i++){
        deque<char>dq;
        for(int w=i;w<sz(s);w++){
            dq.push_back(s[w]);
            mp[dq]++;
        }
    }
    for(int i=0;i<sz(s);i++){
        int l=i,r=i;
        deque<char>dq;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            dq.push_back(s[r]);
            if(l!=r)dq.push_front(s[l]);
            ans=max(ans,mp[dq]*sz(dq));
            r++;
            l--;
        }
    }
    for(int i=1;i<sz(s);i++){
        int l=i-1,r=i;
        deque<char>dq;
        while(l>=0&&r<sz(s)&&s[l]==s[r]){
            dq.push_back(s[r]);
            if(l!=r)dq.push_front(s[l]);
            ans=max(ans,mp[dq]*sz(dq));
            r++;
            l--;
        }
    }
    cout<<ans;
}


void File(){
    ifstream cin(FileS + ".in");
    ofstream cout(FileS + ".out");
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(FileS.size())File();

    int tc=1;
    if(tstc)cin>>tc;

    while(tc--){
        dothethingythatfindsthesolutiontotheproblem();
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27