oj.uz

Submission #253626

# Submission time Handle Problem Language Result Execution time Memory
253626 2020-07-28T13:16:16 Z GREGOIRELC Miners (IOI07_miners) C++14
100 / 100
 343 ms 100984 KB 
#include <iostream>
#include <map>

using namespace std;

const int MAX_FOOD = 1e5 + 1;
const int MAX_SITU = 4 * 4 * 4 * 4;
const int INF = 1e9 + 7;

int nbFood;
int dp[MAX_FOOD][4][4][4][4];
int maxi = 0;
string seq;

int main()
{
	ios::sync_with_stdio(false);

	cin >> nbFood;
	cin >> seq;
	for(int i = 0; i <= nbFood; i++)
	{
		for(int j = 0; j < MAX_SITU; j++)
		{
			int k = j;
			int ad1 = k % 4; k /= 4;
			int d1 = k % 4; k /= 4;
			int ad2 = k % 4; k /= 4;
			int d2 = k % 4;
			dp[i][ad1][d1][ad2][d2] = -INF;
		}
	}
	bool dv[4];
	dp[0][0][0][0][0] = 0;
	for(int curFood = 0; curFood < nbFood; curFood++)
	{
		int valFood;
		if(seq[curFood] == 'M')
		{
			valFood = 1;
		}
		else if(seq[curFood] == 'B')
		{
			valFood = 2;
		}
		else
		{
			valFood = 3;
		}
		for(int situ = 0; situ < MAX_SITU; situ++)
		{
			int k = situ;
			int ad1 = k % 4; k /= 4;
			int d1 = k % 4; k /= 4;
			int ad2 = k % 4; k /= 4;
			int d2 = k % 4; k /= 4;
			int compt = 0;
			for(int i = 0; i < 4; i++)
			{
				dv[i] = false;
			}
			dv[ad1] = true;
			dv[d1] = true;
			dv[valFood] = true;
			for(int i = 1; i < 4; i++)
			{
				if(dv[i])
				{
					compt++;
				}
			}
			//cout << curFood << " " << ad1 << " " << d1 << " " << ad2 << " " << d2 << " " << dp[curFood][ad1][d1][ad2][d2] << " " << valFood << endl;
			dp[curFood + 1][d1][valFood][ad2][d2] = max(dp[curFood + 1][d1][valFood][ad2][d2], dp[curFood][ad1][d1][ad2][d2] + compt);
			maxi = max(maxi, dp[curFood + 1][d1][valFood][ad2][d2]);
			compt = 0;
			for(int i = 0; i < 4; i++)
			{
				dv[i] = false;
			}
			dv[ad2] = true;
			dv[d2] = true;
			dv[valFood] = true;
			for(int i = 1; i < 4; i++)
			{
				if(dv[i])
				{
					compt++;
				}
			}
			dp[curFood + 1][ad1][d1][d2][valFood] = max(dp[curFood + 1][ad1][d1][d2][valFood], dp[curFood][ad1][d1][ad2][d2] + compt);
			maxi = max(maxi, dp[curFood + 1][ad1][d1][d2][valFood]);
		}
	}
	cout << maxi << endl;
}

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 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 4 ms 1280 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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