Submission #76760

#	Time	Username	Problem	Language	Result	Execution time	Memory
76760		MohamedAhmed0	Miners (IOI07_miners)	C++14	100 / 100	300 ms	109100 KiB

miners

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5+5 ;

int n , ans = 0;
string s ;

int dp[MAX][4][4][4][4] ;

int diff(int a , int b , int c)
{
    int x = 3 , y = (a == 0) + (b == 0) + (c == 0);
    if(a == b || b == c || c == a)
        x = 2 ;
    if(y == 2)
        x = 1 ;
    if(y == 1)
        x--;
    if(a == b && b == c)
        x = 1 ;
    return x;
}

int solve(int idx , int prev , int prev1 , int prev2 , int prev3)
{
    if(idx == n)
        return 0 ;
    int &ret = dp[idx][prev][prev1][prev2][prev3] ;
    if(ret != -1)
        return ret ;
    int choice1 = 0 , choice2 = 0 ;
    int type ;
    if(s[idx] == 'B')
        type = 1 ;
    else if(s[idx] == 'M')
        type = 2 ;
    else
        type = 3 ;
    choice1 = solve(idx + 1 , type , prev , prev2 , prev3) + diff(prev , prev1 , type);
    choice2 = solve(idx + 1 , prev , prev1 , type , prev2) + diff(prev2 , prev3 , type);
    return (ret = max(choice1 , choice2));
}

int main()
{
    memset(dp , -1 , sizeof(dp));
    cin>>n ;
    cin>>s ;
    cout<<solve(0 , 0 , 0 , 0 , 0)<<"\n";
    return 0 ;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8