oj.uz

Submission #645185

# Submission time Handle Problem Language Result Execution time Memory
645185 2022-09-26T11:50:13 Z ymm Miners (IOI07_miners) C++17
100 / 100
 218 ms 436 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 360 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 340 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 376 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 412 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 436 KB Output is correct