oj.uz

Submission #207976

# Submission time Handle Problem Language Result Execution time Memory
207976 2020-03-09T15:42:54 Z DodgeBallMan Miners (IOI07_miners) C++14
100 / 100
 251 ms 1144 KB 
#include <bits/stdc++.h>

using namespace std; 

int dp[2][4][4][4][4], a[101000];
int n, ans;
string s;
int cal( int a, int b, int c )
{
	int ret = 0;
	if(a == 1 || b == 1 || c == 1) ret++;
	if(a == 2 || b == 2 || c == 2) ret++;
	if(a == 3 || b == 3 || c == 3) ret++;
	return ret;
}
int main()
{
	scanf("%d",&n);
	cin >> s;
	for( int i = 1 ; i <= n ; i++ ){
		if( s[i-1] == 'M' )a[i] = 1;
		else if( s[i-1] == 'F' )a[i] = 2;
		else a[i] = 3;
	}
	for( int i = 0 ; i < 2 ; i++ )for( int j = 0 ; j < 4 ; j++ )for( int k = 0 ; k < 4 ; k++ )for( int l = 0 ; l < 4 ; l++ )for( int m = 0 ; m < 4 ; m++ )dp[i][j][k][l][m] = -999999999;
	dp[1][0][a[1]][0][0] = dp[1][0][0][0][a[1]] = 1;
	for( int i = 2 ; i <= n ; i++ ){
		for( int j = 0 ; j < 4 ; j++ )for( int k = 0 ; k < 4 ; k++ )for( int l = 0 ; l < 4 ; l++ )for( int m = 0 ; m < 4 ; m++ ){
			dp[i%2][l][a[i]][j][k] = max( dp[(i+1)%2][m][l][j][k] + cal( m, l, a[i] ), dp[i%2][l][a[i]][j][k] );
		}
		for( int j = 0 ; j < 4 ; j++ )for( int k = 0 ; k < 4 ; k++ )for( int l = 0 ; l < 4 ; l++ )for( int m = 0 ; m < 4 ; m++ ){
			dp[i%2][j][k][l][a[i]] = max( dp[(i+1)%2][j][k][m][l] + cal( m, l, a[i] ), dp[i%2][j][k][l][a[i]] );
		}
	}
	for( int i = 0 ; i < 4 ; i++ )for( int j = 0 ; j < 4 ; j++ )
		for( int k = 0 ; k < 4 ; k++ )for( int l = 0 ; l < 4 ; l++ ){
			ans = max( ans, dp[n%2][i][j][k][l] );
		}
	printf("%d",ans);
	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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