Submission #1346506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1346506		vidux	Miners (IOI07_miners)	C++17	100 / 100	110 ms	652 KiB

miners

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        int n; cin >> n;
        string s; cin >> s;
        vvi dp(16, vi(16, -1e9));
        dp[0][0] = 0;
        vi id(256);
        id['F'] = 1;
        id['M'] = 2;
        id['B'] = 3;
        for (int i = 0; i < n; i++) {
                auto dp2 = dp;
                for (int m1 = 0; m1 < 16; m1++) {
                        for (int m2 = 0; m2 < 16; m2++) {
                                if (dp[m1][m2] < 0) continue;
                                int x = id[s[i]];
                                int c1 = __builtin_popcount(((1<<x) | (1<<(m1>>2)) | (1<<(m1&3)))&~1);
                                int c2 = __builtin_popcount(((1<<x) | (1<<(m2>>2)) | (1<<(m2&3)))&~1);
                                int nm1 = (m1>>2)|(x<<2);
                                int nm2 = (m2>>2)|(x<<2);
                                dp2[nm1][m2] = max(dp2[nm1][m2], dp[m1][m2]+c1);
                                dp2[m1][nm2] = max(dp2[m1][nm2], dp[m1][m2]+c2);
                        }
                }
                swap(dp, dp2);
        }
        int ans = 0;
        for (int m1 = 0; m1 < 16; m1++) for (int m2 = 0; m2 < 16; m2++) ans = max(ans, dp[m1][m2]);
        cout << ans << endl;
}

• 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