oj.uz

Submission #109244

# Submission time Handle Problem Language Result Execution time Memory
109244 2019-05-05T18:36:06 Z amiratou Miners (IOI07_miners) C++14
100 / 100
 266 ms 888 KB 
#include <iostream>
#include <algorithm>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int n;
int DP[2][4][4][4][4];
int A[100002];
char c;

int t( int a, int b, int c ){
	int ret = 0;
	for( int i = 1; i <= 3; i++ )
		if( a == i || b == i || c == i )
			ret++;
	return ret;
}

int main(){
	
	optimizar_io
	cin >> n;
	for( int i = 1; i <= n; i++ ){
		cin >> c;
		if( c == 'M' )
			A[i] = 1;
		if( c == 'B' )
			A[i] = 2;
		if( c == 'F' )
			A[i] = 3;
	}
	
	int a = 0, b = 1;
	int i, x, y, r, s;
	for( i = n; i; i-- ){
		swap( a, b );
		//cout << a << " " << b << "\n";
		//cout << DP[b][0][1][0][0] << " " << DP[b][0][0][0][1] << "\n";
		for( x = 0; x < 4; x++ )
			for( y = 0; y < 4; y++ )
				for( r = 0; r < 4; r++ )
					for( s = 0; s < 4; s++ )
						DP[a][x][y][r][s] = max( DP[b][y][ A[i] ][r][s] + t( x, y, A[i] ), DP[b][x][y][s][ A[i] ] + t( r, s, A[i] ) );
	}
	cout << DP[a][0][0][0][0] << "\n";
	
	return 0;
	
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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