oj.uz

Submission #123271

# Submission time Handle Problem Language Result Execution time Memory
123271 2019-07-01T03:07:02 Z turbat Miners (IOI07_miners) C++14
100 / 100
 221 ms 100832 KB 
#include <bits/stdc++.h>
using namespace std;

int dp[100005][4][4][4][4], n, ans;
string st;

int main (){
	cin >> n >> st;
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0][0] = 0;
	for (int i = 1;i <= n;i++){
		int f;
		if (st[i - 1] == 'M') f = 2;
		if (st[i - 1] == 'B') f = 4;
		if (st[i - 1] == 'F') f = 8;
		for (int m11 = 0;m11 < 4;m11++)
			for (int m12 = 0;m12 < 4;m12++)
				for (int m21 = 0;m21 < 4;m21++)
					for (int m22 = 0;m22 < 4;m22++)
						if (dp[i - 1][m11][m12][m21][m22] != -1){
							int job = dp[i - 1][m11][m12][m21][m22];
							int s1 = 0, s2 = 0;
							int c1 = (1<<m11) | (1<<m12) | f;
							int c2 = (1<<m21) | (1<<m22) | f;
							for (int bit = 1;bit < 4;bit++){
								if ((1<<bit) & c1) s1++;
								if ((1<<bit) & c2) s2++;
							}
							int to = log2(f);
							dp[i][m12][to][m21][m22] = max(dp[i][m12][to][m21][m22], job + s1);
							dp[i][m11][m12][m22][to] = max(dp[i][m11][m12][m22][to], job + s2);
							ans = max({ans, job + s1, job + s2});
						}
	}
	cout << ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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