Submission #618804

#	Time	Username	Problem	Language	Result	Execution time	Memory
618804		1ne	Miners (IOI07_miners)	C++14	84 / 100	1240 ms	524288 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 0;
		else if (u == 'B')return 1;
		return 2;
	};
	vector<int>a(2,-1),b(2,-1);
	vector<map<vector<int>,map<vector<int>,int>>>dp(n + 1),came(n + 1);
	function<int(int,vector<int>,vector<int>)>solve = [&](int u,vector<int>arr,vector<int>brr){
		if (u == n)return 0;
		if (came[u][arr][brr])return dp[u][arr][brr];
		came[u][arr][brr] = true;
		int temp = getid(s[u]);
		vector<int>crr(2);
		crr[0] = arr[1];
		crr[1] = temp;
		vector<int>drr(2);
		drr[0] = brr[1];
		drr[1] = temp;
		int cnts = 0,cnts2 = 0;
		if (arr[0] != -1)cnts++;
		if (arr[1] != -1 && arr[1]!=arr[0])cnts++;
		if (temp!=arr[0] && temp!=arr[1])cnts++;
		if (brr[0] != -1)cnts2++;
		if (brr[1] != -1 && brr[1]!=brr[0])cnts2++;
		if (temp!=brr[0] && temp!=brr[1])cnts2++;
		long long ans = max(solve(u + 1,crr,brr) + cnts , solve(u + 1,arr,drr) + cnts2);
		return dp[u][arr][brr] = ans; 
	};
	cout<<solve(0,a,b)<<'\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: 0 / 8
• Subtask 12: 0 / 8