oj.uz

Submission #836007

# Submission time Handle Problem Language Result Execution time Memory
836007 2023-08-24T04:47:40 Z Halym2007 Miners (IOI07_miners) C++11
100 / 100
 172 ms 664 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
const int INF = 1e9 + 10;
string s;
int n, mx, c;
int dp[4][4][4][4], new_dp[4][4][4][4];
int vis[4];

int f (int x, int y, int z) {
	if (x) 
		vis[x] = 1;
	if (y)
		vis[y] = 1;
	if (z) 
		vis[z] = 1;
	int jj = vis[1] + vis[2] + vis[3];
	vis[1] = vis[2] = vis[3] = 0;
	return jj;	
}


int main() {
//	freopen("input.in", "r", stdin);
	cin >> n >> s;
//	cout << n << " " << s << "\n"; 
	for (int x = 0; x < 4; ++x) 
		for (int y = 0; y < 4; ++y) 
			for (int xp = 0; xp < 4; ++xp)	
				for (int yp = 0; yp < 4; ++yp)
					dp[x][y][xp][yp] = -INF;
	dp[0][0][0][0] = 0;
	for (int i = 0; i < n; ++i) { // integer c 
		for (int x = 0; x < 4; ++x) 
			for (int y = 0; y < 4; ++y) 
				for (int xp = 0; xp < 4; ++xp)	
					for (int yp = 0; yp < 4; ++yp)
						new_dp[x][y][xp][yp] = -INF;
		if (s[i] == 'M') c = 1;
        else if(s[i] == 'F') c = 2;
        else c = 3;
		for (int x = 0; x <= 3; ++x) {
			for (int y = 0; y <= 3; ++y) {
				for (int xp = 0; xp <= 3; ++xp)	{
					for (int yp = 0; yp <= 3; ++yp) {
						new_dp[y][c][xp][yp] = max(new_dp[y][c][xp][yp], dp[x][y][xp][yp] + f(x, y, c));
						new_dp[x][y][yp][c] = max(new_dp[x][y][yp][c], dp[x][y][xp][yp] + f(xp, yp, c));
//						if (i == n-1)
//							mx = max ({new_dp[x][y][yp][c], new_dp[y][c][xp][yp], mx});
					}
				}
			}
		}
		for (int x = 0; x <= 3; ++x) {
			for (int y = 0; y <= 3; ++y) {
				for (int xp = 0; xp <= 3; ++xp)	{
					for (int yp = 0; yp <= 3; ++yp) {
						dp[x][y][xp][yp] = new_dp[x][y][xp][yp];
					}
				}
			}
		}
	 }
	for (int x = 0; x < 4; x++)
        for (int y = 0; y < 4; y++)
            for (int xp = 0; xp < 4; xp++)
                for (int yp = 0; yp < 4; yp++)
                    mx = max(mx, dp[x][y][xp][yp]);
	 cout << mx << "\n";
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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