Submission #645185

#	Time	Username	Problem	Language	Result	Execution time	Memory
645185		ymm	Miners (IOI07_miners)	C++17	100 / 100	218 ms	436 KiB

miners

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100010;
const int inf = 1e7;
int n;
int dp[2][64][64];

int get_id(char c)
{
	switch (c) {
	case 'M': return 1;
	case 'B': return 2;
	case 'F': return 4;
	default : return 0;
	}
}

int get_val(int pre, int id)
{
	int msk = (pre&0b111) | ((pre>>3)&0b111) | (id&0b111);
	return (msk&1) + ((msk>>1)&1) + ((msk>>2)&1);
}

int new_pre(int pre, int id)
{
	return ((pre<<3)&0b111000) ^ (id&0b111);
}

int make_pre(int id1, int id2)
{
	return id1 ^ (id2<<3);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	memset(dp, -32, sizeof(dp));
	dp[0][0][0] = 0;
	cin >> n;
	Loop (i,0,n) {
		memset(dp[!(i&1)], -32, sizeof(dp[0]));
		char c;
		cin >> c;
		int id = get_id(c);
		for (int a : {0, 1, 2, 4}) for (int b : {0, 1, 2, 4}) {
			for (int x : {0, 1, 2, 4}) for (int y : {0, 1, 2, 4}) {
				int pre1 = make_pre(a, b);
				int pre2 = make_pre(x, y);
				int npr1 = new_pre(pre1, id);
				int npr2 = new_pre(pre2, id);
				dp[!(i&1)][npr1][pre2] = max(dp[!(i&1)][npr1][pre2], dp[i&1][pre1][pre2] + get_val(pre1, id));
				dp[!(i&1)][pre1][npr2] = max(dp[!(i&1)][pre1][npr2], dp[i&1][pre1][pre2] + get_val(pre2, id));
			}
		}
	}
	int ans = 0;
	Loop (i,0,64) Loop (j,0,64)
		ans = max(ans, dp[n&1][i][j]);
	cout << ans << '\n';
}

• 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