Submission #707781

#	Time	Username	Problem	Language	Result	Execution time	Memory
707781		TAhmed33	Miners (IOI07_miners)	C++98	84 / 100	1569 ms	1104 KiB

miners

#include <bits/stdc++.h>
using namespace std;
int n;
vector <int> adds;
int main () {
	string s;
	cin >> n >> s;
	for (auto i : s) {
		if (i == 'M') adds.push_back(1);
		else if (i == 'F') adds.push_back(2);
		else adds.push_back(3);
	}
	int dp[4][4][4][4][2] = {};
	for (int i = n - 1; i >= 0; i--) {
		for (int a = 0; a <= 3; a++) {
			for (int b = 0; b <= 3; b++) {
				for (int c = 0; c <= 3; c++) {
					for (int d = 0; d <= 3; d++) {
						map <int, int> distinct;
						if (a != 0) distinct[a]++;
						if (b != 0) distinct[b]++;
						distinct[adds[i]]++;
						int x = dp[b][adds[i]][c][d][1] + (int)distinct.size();
						distinct.clear();
						if (c != 0) distinct[c]++;
						if (d != 0) distinct[d]++;
						distinct[adds[i]]++;
						dp[a][b][c][d][0] = max(x, dp[a][b][d][adds[i]][1] + (int)distinct.size());
					}
				}
			}
		}
		for (int a = 0; a <= 3; a++) {
			for (int b = 0; b <= 3; b++) {
				for (int c = 0; c <= 3; c++) {
					for (int d = 0; d <= 3; d++) {
						dp[a][b][c][d][1] = dp[a][b][c][d][0];
					}
				}
			}
		}
	}
	cout << dp[0][0][0][0][1] << '\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: 0 / 8
• Subtask 12: 0 / 8