제출 #1048239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048239		tamir1	Miners (IOI07_miners)	C++17	100 / 100	520 ms	117076 KiB

miners

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],i,dp[100001][4][4][4][4];
string s;
int val(vector<int> v){
	set<int> s;
	for(int x:v){
		if(x) s.insert(x);
	}
	return s.size();
}
int rec(int idx,int a1,int a2,int b1,int b2){
	if(idx==n) return 0;
	int &res=dp[idx][a1][a2][b1][b2];
	if(res!=-1) return res;
	int m1,m2;
	m1=val({a1,a2,a[idx]});
	m2=val({b1,b2,a[idx]});
	return res=max(rec(idx+1,a[idx],a1,b1,b2)+m1,rec(idx+1,a1,a2,a[idx],b1)+m2);
}
int main(){
	memset(dp,-1,sizeof dp);
	cin >> n >> s;
	for(i=0;i<n;i++){
		if(s[i]=='M') a[i]=1;
		if(s[i]=='B') a[i]=2;
		if(s[i]=='F') a[i]=3;
	}
	cout << rec(0,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