제출 #1118142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118142		overwatch9	Miners (IOI07_miners)	C++17	100 / 100	126 ms	136784 KiB

miners

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
int dp[maxn][4][4][4][4];
bool ready[maxn][4][4][4][4];
string s;
int n;
int get_num(char c) {
    if (c == 'M')
        return 1;
    if (c == 'F')
        return 2;
    else
        return 3;
} 
int get_score(int a, int b, int c) {
    if (a == 0) {
        if (b == 0) {
            if (c == 0)
                return 0;
            return 1;
        } else {
            if (b == c)
                return 1;
            return 2;
        }
    } else {
        if (a == b) {
            if (b == c) 
                return 1;
            return 2;
        } else {
            if (a == c) {
                return 2;
            } else {
                if (b == c)
                    return 2;
                return 3;
            }
        }
    }
}
int solve(int i, int a, int b, int c, int d) {
    if (i > n)
        return 0;
    if (ready[i][a][b][c][d])
        return dp[i][a][b][c][d];
    int ans = 0;
    int x = get_num(s[i]);
    int score1 = get_score(a, b, x);
    int score2 = get_score(c, d, x);
    ans = max({ans, solve(i+1, b, x, c, d) + score1, solve(i+1, a, b, d, x) + score2});
    ready[i][a][b][c][d] = true;
    dp[i][a][b][c][d] = ans;
    return ans;
}
int main() {
    cin >> n >> s;
    s = "." + s;
    cout << solve(1, 0, 0, 0, 0) << '\n';
}

• 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