oj.uz

Submission #464042

# Submission time Handle Problem Language Result Execution time Memory
464042 2021-08-12T09:55:59 Z dutch Miners (IOI07_miners) C++17
100 / 100
 735 ms 400 KB 
#include <bits/stdc++.h>
using namespace std;
#define F(z) for(int z=0; z<4; ++z)
#define remax(x, y) x = max(x, y)
#define fill(z) F(a) F(b) F(x) F(y) z[a][b][x][y] = -2e9

int cost(int a, int b, int c){
	int res = 0;
	for(int i : {0, 1, 2}) res += (a == i) || (b == i) || (c == i);
	return res;
}

int n, dp[4][4][4][4], c[4][4][4][4], ans;
char inp;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	fill(dp);
	dp[3][3][3][3] = 0;
	for(int i=0, j; i<n; ++i){
		cin >> inp; j = (inp > 'B') + (inp > 'F');
		fill(c);
		for(int k : {j, 3}) F(a) F(b) F(x) F(y){
			remax(c[b][k][x][y], dp[a][b][x][y] + cost(a, b, k));
			remax(c[a][b][y][k], dp[a][b][x][y] + cost(x, y, k));
		}
		F(a) F(b) F(x) F(y)
			remax(ans, dp[a][b][x][y] = c[a][b][x][y]);
	}
	cout << ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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