oj.uz

Submission #477087

# Submission time Handle Problem Language Result Execution time Memory
477087 2021-09-30T07:34:09 Z SlavicG Miners (IOI07_miners) C++17
100 / 100
 195 ms 608 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 10;
int dp[4][4][4][4];
int prev_dp[4][4][4][4];

void solve()
{  
    forn(a,4)forn(b,4)forn(c,4)forn(d,4)dp[a][b][c][d] = prev_dp[a][b][c][d] = -100000;
    int n;
    string s;
    cin >> n >> s;

    prev_dp[0][0][0][0] = 0;
    for(int i = 1;i <= n;++i){
        int x;
        if(s[i - 1] == 'M')x = 1;
        else if(s[i - 1] == 'B')x = 2;
        else x = 3;
        for(int a = 0;a < 4;++a){
            for(int b = 0;b < 4;++b){
                for(int c = 0;c < 4;++c){
                    for(int d = 0;d < 4;++d){
                        int add = 1;
                        if((x != a && a) && (x != b && b) && (a != b && a && b))add = 3;
                        else if((x != a && a) || (x != b && b) || (a != b && a && b))add = 2;
                        dp[x][a][c][d] = max(dp[x][a][c][d], prev_dp[a][b][c][d] + add);

                        add = 1;
                        if((x != c && c) && (x != d && d) && (c != d && c && d))add = 3;
                        else if((x != c && c) || (x != d && d) || (c != d && c && d))add = 2;
                        dp[a][b][x][c] = max(dp[a][b][x][c], prev_dp[a][b][c][d] + add);
                    }
                }
            }
        }

        for(int a = 0;a < 4;++a){
            for(int b = 0;b < 4;++b){
                for(int c = 0;c < 4;++c){
                    for(int d = 0;d < 4;++d){
                        prev_dp[a][b][c][d] = dp[a][b][c][d];
                        dp[a][b][c][d] = -100000;
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int a = 0;a < 4;++a){
        for(int b = 0;b < 4;++b){
            for(int c = 0;c < 4;++c){
                for(int d = 0;d < 4;++d){
                    ans = max(ans, prev_dp[a][b][c][d]);
                }
            }
        }
    }
    cout << ans << "\n";
}  
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 332 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 348 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 332 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 560 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 608 KB Output is correct