oj.uz

Submission #253698

# Submission time Handle Problem Language Result Execution time Memory
253698 2020-07-28T14:26:25 Z Mounir Miners (IOI07_miners) C++14
100 / 100
 1175 ms 201032 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2304 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10368 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 20424 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 50416 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 150904 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1175 ms 201032 KB Output is correct