제출 #1068258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068258		Halym2007	Miners (IOI07_miners)	C++17	100 / 100	245 ms	111848 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 = 1e5 + 5;
int dp[N][4][4][4][4], n;
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;
}

int solve (int idx, int x, int y, int x1, int y1) {
	if (idx == n + 1) {
		return 0;
	}
	if (~dp[idx][x][y][x1][y1]) return dp[idx][x][y][x1][y1];
	int val = 0;
	if (s[idx] == 'F') val = 1;
	else if (s[idx] == 'M') val = 2;
	else val = 3;
	int ans1 = solve(idx + 1, y, val, x1, y1) + jogap(x, y, val), ans2 = solve (idx + 1, x, y, y1, val) + jogap (x1, y1, val);
	return dp[idx][x][y][x1][y1] = max (ans1, ans2);
}


int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> s;
	s = " " + s;
	memset (dp, -1, sizeof(dp));
	
	cout << solve (1, 0, 0, 0, 0);	
}

• 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