oj.uz

Submission #396092

# Submission time Handle Problem Language Result Execution time Memory
396092 2021-04-29T12:50:16 Z Sorting Miners (IOI07_miners) C++17
100 / 100
 258 ms 844 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;
template<class T> void check_max(T &a, const T b){ a = (a > b) ? a : b; }

int dp[2][16][16];
int n, a[N];
string s;

int calc_points(int t1, int t2, int t3){
    if(t1 == 0) t1 = t3;
    if(t2 == 0) t2 = t3;
    if(t1 == t2  && t2 == t3) return 1;
    if(t1 == t2 || t1 == t3 || t2 == t3) return 2;
    return 3;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s;
    for(int i = 0; i < n; ++i){
        if(s[i] == 'M') a[i] = 1;
        else if(s[i] == 'F') a[i] = 2;
        else a[i] = 3;
    }

    for(int i = n - 1; i >= 0; --i){
        int c_idx = (i & 1), next_idx = ((i + 1) & 1);
        for(int m1 = 0; m1 < 16; ++m1){
            for(int m2 = 0; m2 < 16; ++m2){
                int &ans = dp[c_idx][m1][m2];
                ans = 0;

                int t1, t2, t3;
                t1 = m1 / 4, t2 = m1 % 4, t3 = a[i];
                check_max(ans, calc_points(t1, t2, t3) + dp[next_idx][(m1 % 4) * 4 + a[i]][m2]);

                t1 = m2 / 4, t2 = m2 % 4, t3 = a[i];
                check_max(ans, calc_points(t1, t2, t3) + dp[next_idx][(m2 % 4) * 4 + a[i]][m1]);
                //cout << ans << " - " << i << " " << m1 << " " << m2 << endl; 
            }
        }
    }

    cout << dp[0][0][0] << "\n";
}

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 3 ms 328 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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