Submission #76760

# Submission time Handle Problem Language Result Execution time Memory
76760 2018-09-17T14:10:12 Z MohamedAhmed0 Miners (IOI07_miners) C++14
100 / 100
300 ms 109100 KB
#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 ;
}
# Verdict Execution time Memory Grader output
1 Correct 86 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 114 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 86 ms 100600 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 79 ms 100704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 82 ms 100704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 82 ms 100704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 82 ms 100960 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 85 ms 101164 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 99 ms 101624 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 147 ms 102812 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 197 ms 106936 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 300 ms 109100 KB Output is correct