oj.uz

Submission #372733

# Submission time Handle Problem Language Result Execution time Memory
372733 2021-03-01T11:56:02 Z Drew_ Miners (IOI07_miners) C++14
100 / 100
 155 ms 100864 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

ld const PI = 4*atan((ld)1);
const int MAX = 1e5 + 7;

int dp[MAX][4][4][4][4];

int main()
{
	fastio;
	memset(dp, -1, sizeof(dp));


	int n;
	cin >> n;

	string s;
	cin >> s;

	dp[0][0][0][0][0] = 0;
	for (int i = 0; i < n; ++i)
	{
		int nxt;
		if (s[i] == 'M') nxt = 1;
		if (s[i] == 'B') nxt = 2;
		if (s[i] == 'F') nxt = 3;

		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)
					{
						if (dp[i][a][b][c][d] == -1)
							continue;
						
						int coal;
						//giving to the first mine
						coal = 0;
						for (int x = 1; x <= 3; ++x)
							coal += (x == a || x == b || x == nxt);
						dp[i+1][b][nxt][c][d] = max(dp[i+1][b][nxt][c][d], coal + dp[i][a][b][c][d]);

						//giving to the second mine
						coal = 0;
						for (int x = 1; x <= 3; ++x)
							coal += (x == c || x == d || x == nxt);
						dp[i+1][a][b][d][nxt] = max(dp[i+1][a][b][d][nxt], coal + dp[i][a][b][c][d]);

					}
				}
			}
		}
	}

	int res = 0;
	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)
					res = max(res, dp[n][a][b][c][d]);
	cout << res << '\n';
	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:57:34: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |        coal += (x == a || x == b || x == nxt);
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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