Submission #863869

#	Time	Username	Problem	Language	Result	Execution time	Memory
863869		VN_AnhTuan	Palinilap (COI16_palinilap)	C++14	17 / 100	1058 ms	56652 KiB

palinilap

//  Author : Nguyen Anh Tuan - THPT Chuyen Bac Giang - Train VOI 2023/2024

#include<bits/stdc++.h>
#define file(NAME) {freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout);}
#define foru(i, a, b) for(int i=(a);i<=(b);i++)
#define ford(i, a, b) for(int i=(a);i>=(b);i--)
#define rep(i, n) for(int i=(1);i<=(n);i++)
#define fi first
#define se second
#define mp make_pair
#define SZ(v) ((int)((v).size()))
#define all(v) v.begin(),v.end()
#define RR(X) X.resize(unique(all(X)) - begin(X))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;

namespace IO
{
    #define getchar() (ipos==iend and (iend=(ipos=_ibuf)+fread(_ibuf,1,__bufsize,stdin),ipos==iend)?EOF:*ipos++)
    #define putchar(ch) (opos==oend?fwrite(_obuf,1,__bufsize,stdout),opos=_obuf:0,*opos++=(ch))
    #define __bufsize (1<<20)
    char _ibuf[__bufsize],_obuf[__bufsize],_stk[20];
    char *ipos=_ibuf,*iend=_ibuf,*opos=_obuf,*oend = _obuf+__bufsize,*stkpos = _stk;
    struct END{~END(){fwrite(_obuf,1,opos-_obuf,stdout);}}__;
    inline void read(int &x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
    inline void lread(ll&x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void lwrite(ll x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
};

void maximum(ll &a, ll b) {if(b > a) a = b;}
void minimum(ll &a, ll b) {if(b < a) a = b;}
bool bit(int x, int i) {return (x >> i) & 1;}

//-----------------------------------------------------------------------------------
//      END OF TEMPLATE
//-----------------------------------------------------------------------------------
//      Nguyen Anh Tuan - AnhTuan_BG
//      PRAY FOR VOI 2023
//-----------------------------------------------------------------------------------

string s;
int n;

namespace sub1
{
    const int maxn = 5005;
    bool f[maxn][maxn];
    ll ans = 0;

    ll Calc()
    {
        //cout << s << "\n";
        int tmp = 0;
        foru(i, 1, n) foru(j, 1, n) f[i][j] = 0;
        ford(i, n, 1)
        {
            f[i][i] = 1;
            if(s[i] == s[i + 1]) f[i][i + 1] = 1;
            foru(j, i + 2, n)
            {
                if(s[i] == s[j]) f[i][j] = f[i + 1][j - 1];
            }
        }

        foru(i, 1, n) foru(j, i, n) tmp = tmp + f[i][j];
        //cout << tmp << "\n";
        return tmp;
    }

    void solve()
    {
        ans = Calc();
        foru(i, 1, n)
        {
            char x = s[i];
            foru(j, 0, 25)
            {
                if(j == x - 'a') continue;
                s[i] = char('a' + j);
                ans = max(ans, Calc());
            }
            s[i] = x;
        }
        cout << ans;
    }
}

namespace sub2
{
    const int maxn = 5005;
    ll dp[maxn][30];
    bool f[maxn][maxn];
    ll maxx[maxn];

    void solve()
    {
        ford(i, n, 1)
        {
            f[i][i] = 1;
            if(s[i] == s[i + 1]) f[i][i + 1] = 1;
            foru(j, i + 2, n)
            {
                if(s[i] == s[j]) f[i][j] = f[i + 1][j - 1];
            }
        }

        foru(i, 0, 25) dp[1][i] = 1;
        maxx[1] = 1;
        foru(i, 2, n)
        {
            foru(j, 0, 25)
            {
                dp[i][j] = 1;
                if(j == s[i] - 'a') continue;
                foru(k, 1, i - 1)
                {
                    if((k == i - 1 || f[k + 1][i - 1]) && (j == s[k] - 'a'))
                    {
                        //dp[i][j] = dp[i][j] + dp[k][s[k] - 'a'];
                        dp[i][j]++;
                    }

                }
                maxx[i] = max(maxx[i], dp[i][j]);
            }
            //ll sum = 0;
            foru(k, 1, i - 1)
            {
                if(k == i - 1 || f[k + 1][i - 1])
                {
                    //sum = sum + dp[k][s[k] - 'a'];
                    dp[i][s[i] - 'a'] = max(dp[k][s[k] - 'a'] + 1, dp[i][s[i] - 'a']);
                }
            }

//            foru(k, 1, i - 1)
//            {
//                if(k == i - 1 || f[k + 1][i - 1])
//                dp[i][s[i] - 'a'] = max(dp[i][s[i] - 'a'], sum - dp[k][s[k] - 'a'] + maxx[k]);
//            }

            maxx[i] = max(maxx[i], dp[i][s[i] - 'a']);
        }

        foru(i, 1, n)
        {
            foru(j, 0, 25) cout << dp[i][j] << " ";
            cout << "\n";
        }

        cout << maxx[n];
    }
}

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

    cin >> s;
    n = s.size();
    s = " " + s;

    sub1 :: solve();

    return 0;
}

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