Submission #109244

#	Time	Username	Problem	Language	Result	Execution time	Memory
109244		amiratou	Miners (IOI07_miners)	C++14	100 / 100	266 ms	888 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8