제출 #1068435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068435		Halym2007	Miners (IOI07_miners)	C++17	100 / 100	662 ms	748 KiB

miners

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <char, int>
const int N = 2e4 + 5;
int dp[4][4][4][4], n, new_dp[4][4][4][4];
int jog = 0;
string s;
int jogap (int x, int y, int z) {
	int ret = 0;
	vector <int> v(4, 0);
	v[x] = 1;v[y] = 1;v[z] = 1;
	ret = v[1] + v[2] + v[3];
	return ret;
}

void solve (int idx) {
	if (idx == n + 1) return;
//	cout << "1--> " << idx << "\n";
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int l = 0; l < 4; ++l) {
				for (int r = 0; r < 4; ++r) {
					new_dp[i][j][l][r] = -1e9;
				}
			}
		}
	}
	int val = 0;	
	if (s[idx] == 'F') val = 1;
	else if (s[idx] == 'M') val = 2;
	else val = 3;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int l = 0; l < 4; ++l) {
				for (int r = 0; r < 4; ++r) {
//					cout << "men";
//					exit(0);
					new_dp[j][val][l][r] = max (new_dp[j][val][l][r], dp[i][j][l][r] + jogap (i, j, val));
					new_dp[i][j][r][val] = max (new_dp[i][j][r][val], dp[i][j][l][r] + jogap (l, r, val));
//					if (!i and !j and !l and !r) {
//						cout << new_dp[j][val][l][r] << " " << dp[i][j][l][r] << " " << jogap(i, j, val);
//						exit(0);
//					}
//					dp[j][val][l][r] = new_dp[j][val][l][r];
//					dp[i][j][r][val] = new_dp[i][j][r][val];
				}
			}
		}
	}	
//	cout << new_dp[0][3][0][0];
//	exit(0);
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int l = 0; l < 4; ++l) {
				for (int r = 0; r < 4; ++r) {
					dp[i][j][l][r] = new_dp[i][j][l][r];
				}
			}
		}
	}
	solve (idx + 1);
}


int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> s;
	s = " " + s;
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int l = 0; l < 4; ++l) {
				for (int r = 0; r < 4; ++r) {
					dp[i][j][l][r] = -1e9;
				}
			}
		}
	}	
	dp[0][0][0][0] = 0;
	solve(1);
	for (int i = 0; i < 4; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int l = 0; l < 4; ++l) {
				for (int r = 0; r < 4; ++r) {
					jog = max (dp[i][j][l][r], jog);
				}
			}
		}
	}	
//	return cout << dp[]
	cout << jog;
}

• 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