oj.uz

Submission #64676

# Submission time Handle Problem Language Result Execution time Memory
64676 2018-08-05T11:14:56 Z nvmdava Miners (IOI07_miners) C++17
100 / 100
 328 ms 101384 KB 
#include <bits/stdc++.h>
using namespace std;

int dp[100002][4][4][4][4];
int f(char c){
	if(c == 'M'){
		return 1;
	} else if(c == 'B'){
		return 2;
	} else {
		return 3;
	}
}
int mine(int a, int b, int c){
	int s = 0;
	if (a == 1 || b == 1 || c == 1) s++;
	if (a == 2 || b == 2 || c == 2) s++;
	if (a == 3 || b == 3 || c == 3) s++;
	return s;
}
int main(){
	int len, i, w, j, l, m, n, k, t;
	cin>>len;
	string s;
	cin>>s;
	for(w = 0; w < len; w++){
		t = f(s[w]);
		for(j = 0; j <= 3; j++){
			for(l = 0; l <= 3; l++){
				for(m = 0; m <= 3; m++){
					for(n = 0; n <= 3; n++){
						dp[w + 1][l][t][m][n] = max(dp[w + 1][l][t][m][n], dp[w][j][l][m][n] + mine(j, l, t));
						dp[w + 1][j][l][n][t] = max(dp[w + 1][j][l][n][t], dp[w][j][l][m][n] + mine(m, n, t));
					}
				}
			}
		}
	}
	int mx = -1;
	w = len;
	for(j = 0; j <= 3; j++){
		for(l = 0; l <= 3; l++){
			for(m = 0; m <= 3; m++){
				for(n = 0; n <= 3; n++){
					mx = max(mx, dp[w][j][l][m][n]);
				}
			}
		}
	}
	cout<<mx - 6;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:22:11: warning: unused variable 'i' [-Wunused-variable]
  int len, i, w, j, l, m, n, k, t;
           ^
miners.cpp:22:29: warning: unused variable 'k' [-Wunused-variable]
  int len, i, w, j, l, m, n, k, t;
                             ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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