oj.uz

Submission #283821

# Submission time Handle Problem Language Result Execution time Memory
283821 2020-08-26T07:37:59 Z Bill_00 Miners (IOI07_miners) C++14
100 / 100
 219 ms 680 KB 
#include <bits/stdc++.h>
using namespace std;
int dp[2][4][4][4][4];
int find(int a, int b, int c)
{
	int d[4] = {0};
	d[a]++;
	d[b]++;
	d[c]++;
	int s = 0;
	for(int i = 1; i <= 3; i++) if(d[i] > 0) s++;
	return s;
}
int main()
{	int n, i, j;
	string s;
	cin >> n >> s;
	memset(dp, -1, sizeof(dp));
	dp[0][0][0][0][0] = 0;
	int res = 0;
	int next = 1, now = 0;
	for(i = 0; i < n; i++)
	{
		for(int a = 0; a <= 3; a++)
		for(int b = 0; b <= 3; b++)
		for(int c = 0; c <= 3; c++)
		for(int d = 0; d <= 3; d++)
		if(dp[now][a][b][c][d] != -1){
			int k;
			if(s[i] == 'M') k = 1;
			if(s[i] == 'F') k = 2;
			if(s[i] == 'B') k = 3;
			dp[next][b][k][c][d] = max(dp[next][b][k][c][d], dp[now][a][b][c][d] + find(a, b, k));
			dp[next][a][b][d][k] = max(dp[next][a][b][d][k], dp[now][a][b][c][d] + find(c, d, k));
			res = max(res, dp[next][b][k][c][d]);
			res = max(res, dp[next][a][b][d][k]);
		}
		swap(now, next);
	}
	cout << res;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:15:13: warning: unused variable 'j' [-Wunused-variable]
   15 | { int n, i, j;
      |             ^
miners.cpp:9:5: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
    9 |  d[c]++;
      |  ~~~^
miners.cpp:29:8: note: 'k' was declared here
   29 |    int k;
      |        ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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