제출 #99212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99212		figter001	Miners (IOI07_miners)	C++17	100 / 100	433 ms	210900 KiB

miners

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;

int n,t[nax];
string s;
ll dp[nax][4][4][4][4];

ll calc(int idx,pair<int,int> a,pair<int,int> b){
	if(idx == n)
		return 0;
	ll &ret = dp[idx][a.first][a.second][b.first][b.second];
	if(ret != -1)
		return ret;
	int add = 1;
	if(a.first != 0 && a.first != t[idx])
		add++;
	if(a.second != 0 && a.second != a.first && a.second != t[idx])
		add++;
	ret = calc(idx+1,{a.second,t[idx]},b) + add;
	add = 1;
	if(b.first != 0 && b.first != t[idx])
		add++;
	if(b.second != 0 && b.second != b.first && b.second != t[idx])
		add++;
	ret = max(ret,calc(idx+1,a,{b.second,t[idx]}) + add);
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>s;
	for(int i=0;i<n;i++){
		if(s[i] == 'M')t[i] = 1;
		if(s[i] == 'F')t[i] = 2;
		if(s[i] == 'B')t[i] = 3;
	}
	cout << calc(0,{0,0},{0,0}) << endl;
}

• 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