제출 #618826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618826		1ne	Miners (IOI07_miners)	C++14	100 / 100	231 ms	116452 KiB

miners

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	string s;cin>>s;
	auto getid = [&](char u){
		if (u == 'M')return 1;
		else if (u == 'B')return 2;
		return 3;
	};
	int dp[n][4][4][4][4];
	for (int i = 0;i<n;++i){
		for (int j = 0;j<4;++j){
			for (int k = 0;k<4;++k){
				for (int l = 0;l<4;++l){
					for (int m = 0;m<4;++m){
						dp[i][j][k][l][m] = -1;
					}
				}
			}
		}
	}
	function<int(int,int,int,int,int)>solve = [&](int u,int prev,int prev2,int prev3,int prev4){
		if (u == n)return 0;
		if (dp[u][prev][prev2][prev3][prev4]!=-1)return dp[u][prev][prev2][prev3][prev4];
		int temp = getid(s[u]);
		int cnts = 0,cnts2 = 0;
		if (prev != 0)cnts++;
		if (prev2 != 0 && prev2!=prev)cnts++;
		if (temp!=prev && temp!=prev2)cnts++;
		if (prev3 != 0)cnts2++;
		if (prev4 != 0 && prev4!=prev3)cnts2++;
		if (temp!=prev3 && temp!=prev4)cnts2++;
		long long ans = max(solve(u + 1,prev2,temp,prev3,prev4) + cnts , solve(u + 1,prev,prev2,prev4,temp) + cnts2);
		return dp[u][prev][prev2][prev3][prev4] = ans; 
	};
	cout<<solve(0,0,0,0,0)<<'\n';
	return 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