Submission #253698

#	Time	Username	Problem	Language	Result	Execution time	Memory
253698		Mounir	Miners (IOI07_miners)	C++14	100 / 100	1175 ms	201032 KiB

miners

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define taille(x) (int)x.size()
#define int long long
using namespace std;

map<char, int> conv = {
	{'M', 1},
	{'B', 2},
	{'F', 3}
};

signed main(){
	int lenChaine;
	cin >> lenChaine;
	
	string chaine;
	cin >> chaine;
	
	int dp[lenChaine + 1][4][4][4][4];
	for (int ind = 0; ind <= lenChaine; ++ind)
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j)
				for (int k = 0; k < 4; ++k)
					for (int l = 0; l < 4; ++l)
						dp[ind][i][j][k][l] = -1;
	
	dp[0][0][0][0][0] = 0;
	int maxi = 0;
	for (int ind = 0; ind < lenChaine; ++ind){
		char cara = chaine[ind];
		
		int M = 0;
		
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j)
				for (int k = 0; k < 4; ++k)
					for (int l = 0; l < 4; ++l){
						if (dp[ind][i][j][k][l] == -1) //IMPOSSIBLE
							continue;
						
						int n = conv[cara];
						chmax(M, dp[ind][i][j][k][l]);
						//Mettre dans la premiere chaine
						set<int> vals;
						vals = {i, j, n};
						vals.erase(0);
						chmax(dp[ind + 1][j][n][k][l], dp[ind][i][j][k][l] + taille(vals));
						
						vals = {k, l, n};
						vals.erase(0);
						chmax(dp[ind + 1][i][j][l][n], dp[ind][i][j][k][l] + taille(vals));
					}
		//cout << M << endl;
	}
	
	for (int ind = 0; ind <= lenChaine; ++ind)
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j)
				for (int k = 0; k < 4; ++k)
					for (int l = 0; l < 4; ++l)
						chmax(maxi, dp[ind][i][j][k][l]);
	cout << maxi << endl;
	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