Submission #372733

#	Time	Username	Problem	Language	Result	Execution time	Memory
372733		Drew_	Miners (IOI07_miners)	C++14	100 / 100	155 ms	100864 KiB

miners

#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 (stderr)

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 / 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