Submission #1344711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344711		toast12	Miners (IOI07_miners)	C++20	100 / 100	920 ms	444764 KiB

miners

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> v;

int uniq(int a, int b, int c) {
    set<int> s;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    if (*s.begin() == 0) return s.size()-1;
    return s.size();
}

vector<vector<vector<vector<vector<int>>>>> dp;

int solve(int i, int a, int b, int x, int y) {
    if (i == n) return 0;
    if (dp[i][a][b][x][y] != -1) return dp[i][a][b][x][y];
    int ans = 0;
    ans = max(ans, solve(i+1, b, v[i], x, y) + uniq(a, b, v[i]));
    ans = max(ans, solve(i+1, a, b, y, v[i]) + uniq(x, y, v[i]));
    return dp[i][a][b][x][y] = ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'M') v.push_back(1);
        else if (s[i] == 'F') v.push_back(2);
        else v.push_back(3);
    }
    dp.resize(n, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));
    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