Submission #1194299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194299		Petrix	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	0 ms	320 KiB

palindromic

#include <iostream>
using namespace std;

int dp[100001][4][4][4][4];
int frv[256];

int ce_punem(int a,int b,int c){
    if(!a) a=c;
    if(!b) b=c;
    if(a!=b && a!=c && b!=c) return 3;
    if(a==b && b==c) return 1;
    return 2;
}

int main()
{
    frv['M']=1;frv['B']=2;frv['F']=3;
    int n,i,food11,food21,food12,food22,max1=0;string s;
    cin>>n>>s;
    s=' '+s;
    for(i=0;i<=n;i++){
        for(food11=0;food11<4;food11++){
            for(food21=0;food21<4;food21++){
                for(food12=0;food12<4;food12++){
                    for(food22=0;food22<4;food22++){
                        dp[i][food11][food21][food12][food22]=-1e9;
                    }
                }
            }
        }
    }
    dp[0][0][0][0][0]=0;
    for(i=1;i<=n;i++){
        for(food11=0;food11<4;food11++){///1
            for(food21=0;food21<4;food21++){///1
                for(food12=0;food12<4;food12++){///2
                    for(food22=0;food22<4;food22++){///2
                        ///punem la 1
                        dp[i][food21][frv[s[i]]][food12][food22]=max(dp[i][food21][frv[s[i]]][food12][food22],
                                                                     dp[i-1][food11][food21][food12][food22]+ce_punem(food11,food12,frv[s[i]]));
                        dp[i][food11][food21][food22][frv[s[i]]]=max(dp[i][food11][food21][food22][frv[s[i]]],
                                                                     dp[i-1][food11][food21][food12][food22]+ce_punem(food12,food22,frv[s[i]]));

                    }
                }
            }
        }
    }
    /*
    for(i=1;i<=n;i++){
        for(food11=0;food11<4;food11++){///1
            for(food21=0;food21<4;food21++){///1
                for(food12=0;food12<4;food12++){///2
                    for(food22=0;food22<4;food22++){///2
                        if(dp[i][food11][food21][food12][food22]>0)
                            cout<<i<<"|1: "<<food11<<" "<<food21<<"|2: "<<food12<<" "<<food22<<" "<<dp[i][food11][food21][food12][food22]<<"\n";
                    }
                }
            }
        }
    }*/
    for(food11=0;food11<4;food11++){///1
        for(food21=0;food21<4;food21++){///1
            for(food12=0;food12<4;food12++){///2
                for(food22=0;food22<4;food22++){///2
                    max1=max(max1,dp[n][food11][food21][food12][food22]);
                }
            }
        }
    }
    cout<<max1-1;
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40