Submission #836007

#	Time	Username	Problem	Language	Result	Execution time	Memory
836007		Halym2007	Miners (IOI07_miners)	C++11	100 / 100	172 ms	664 KiB

miners

#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 / 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