oj.uz

Submission #254156

# Submission time Handle Problem Language Result Execution time Memory
254156 2020-07-29T12:17:25 Z vjules Miners (IOI07_miners) C++14
100 / 100
 126 ms 39928 KB 
#include <bits/stdc++.h>
using namespace std;

int longueur;
int type [100001];
int DP [100002][100];

struct Situation	{
	int repasMine1[2];
	int repasMine2[2];
};

inline int SituationToInt (Situation situation)	{
	int repasMine1[2] = {situation.repasMine1[0], situation.repasMine1[1]};;
	int repasMine2[2] = {situation.repasMine2[0], situation.repasMine2[1]};;

	int mine1 = 0;
	if (repasMine1[0] == -1)	{
		repasMine1[0] = repasMine1[1];
	}
	if (repasMine1 [0] == -1)	mine1 = 9;
	else	{
		mine1 = repasMine1[1] + repasMine1[0]*3;
	}

	int mine2 = 0;
	if (repasMine2[0] == -1)	{
		repasMine2[0] = repasMine2[1];
	}
	if (repasMine2 [0] == -1)	mine2 = 9;
	else	{
		mine2 = repasMine2[1] + repasMine2[0]*3;
	}

	return mine2 + mine1*10;
}

inline Situation IntToSituation (int numSituation)	{
	Situation result;
	int mine1 = numSituation/10;
	int mine2 = numSituation%10;

	if (mine1 == 9)	{
		result.repasMine1[0] = -1;
		result.repasMine1[1] = -1;
	}
	else	{
		result.repasMine1[0] = mine1/3;
		result.repasMine1[1] = mine1%3;
	}

	if (mine2 == 9)	{
		result.repasMine2[0] = -1;
		result.repasMine2[1] = -1;
	}
	else	{
		result.repasMine2[0] = mine2/3;
		result.repasMine2[1] = mine2%3;
	}

	return result;
}

inline int nbDiff (int a, int b, int c)	{
	int result = 1;
	if (b != a)	result++;
	if (c != a && c != b)	result++;
	if (a == -1 || b == -1 || c == -1)	result--;
	return result;
}
	





int main() 	{
//	ios:: sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL);
	cin >> longueur;
	for (int iElem = 0; iElem < longueur; iElem++)	{
		char lettre;
		cin >> lettre;
		if (lettre == 'M')	type[iElem] = 0;
		else if (lettre == 'F')	type[iElem] = 1;
		else						type[iElem] = 2;
	}
	for (int numSituation = 0; numSituation < 100; numSituation++)	{
		DP[longueur][numSituation] = 0;
	}
	for (int pos = longueur - 1; pos >= 0; pos--)	{
		for (int numSituation = 0; numSituation < 100; numSituation++)	{
			Situation situation1 = IntToSituation(numSituation);
			Situation situation2 = IntToSituation(numSituation);

			int nbDiff1 = nbDiff(situation1.repasMine1[0], situation1.repasMine1[1], type[pos]);
			int nbDiff2 = nbDiff(situation2.repasMine2[0], situation2.repasMine2[1], type[pos]);

			situation1.repasMine1[0] = situation1.repasMine1[1];
			situation2.repasMine2[0] = situation2.repasMine2[1];

			situation1.repasMine1[1] = type[pos];
			situation2.repasMine2[1] = type[pos];

			int scoreDonne1 = DP[pos+1][SituationToInt(situation1)] + nbDiff1;
			int scoreDonne2 = DP[pos+1][SituationToInt(situation2)] + nbDiff2;

			DP[pos][numSituation] = max(scoreDonne1, scoreDonne2);

//			Situation situation = IntToSituation(numSituation);
//			cout << "en " << pos << " avec (" << situation.repasMine1[0] << " " << situation.repasMine1[1] << ")  (" << situation.repasMine2[0] << " " << situation.repasMine2[1] << ")   -> " << DP[pos][numSituation] << "\n";
		}
	}
	
	cout << DP[0][SituationToInt({{-1,-1},{-1,-1}})] << "\n";
}

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 0 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 760 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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