Submission #123271

#	Time	Username	Problem	Language	Result	Execution time	Memory
123271		turbat	Miners (IOI07_miners)	C++14	100 / 100	221 ms	100832 KiB

miners

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

int dp[100005][4][4][4][4], n, ans;
string st;

int main (){
	cin >> n >> st;
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0][0] = 0;
	for (int i = 1;i <= n;i++){
		int f;
		if (st[i - 1] == 'M') f = 2;
		if (st[i - 1] == 'B') f = 4;
		if (st[i - 1] == 'F') f = 8;
		for (int m11 = 0;m11 < 4;m11++)
			for (int m12 = 0;m12 < 4;m12++)
				for (int m21 = 0;m21 < 4;m21++)
					for (int m22 = 0;m22 < 4;m22++)
						if (dp[i - 1][m11][m12][m21][m22] != -1){
							int job = dp[i - 1][m11][m12][m21][m22];
							int s1 = 0, s2 = 0;
							int c1 = (1<<m11) | (1<<m12) | f;
							int c2 = (1<<m21) | (1<<m22) | f;
							for (int bit = 1;bit < 4;bit++){
								if ((1<<bit) & c1) s1++;
								if ((1<<bit) & c2) s2++;
							}
							int to = log2(f);
							dp[i][m12][to][m21][m22] = max(dp[i][m12][to][m21][m22], job + s1);
							dp[i][m11][m12][m22][to] = max(dp[i][m11][m12][m22][to], job + s2);
							ans = max({ans, job + s1, job + s2});
						}
	}
	cout << ans;
}

• 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