Submission #739386

#	Time	Username	Problem	Language	Result	Execution time	Memory
739386		Toxtaq	Miners (IOI07_miners)	C++17	84 / 100	1572 ms	401356 KiB

miners

#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<complex>
#include<map>
#include<iomanip>
#include<set>
using namespace std;
/// M-1,B-2,F-3
int main(){
	int n;
	cin >> n;
	map<char,int>mp;
	string s;
	cin >> s;
	mp['M']=1;
	mp['B']=2;
	mp['F']=3;
	long long table[2][4][4][4][4][n+1];
	for(int i = n-1;i>=0;--i){
		for(int j = 0;j<2;++j){
			for(int l = 0;l<4;++l){
				for(int r = 0;r<4;++r){
					for(int k=0;k<4;++k){
						for(int z = 0;z<4;++z){
							table[j][l][r][k][z][i]=-1e18;
						}
					}
				}
			}
		}
	}
	for(int j = 0;j<2;++j){
			for(int l = 0;l<4;++l){
				for(int r = 0;r<4;++r){
					for(int k=0;k<4;++k){
						for(int z = 0;z<4;++z){
							table[j][l][r][k][z][n]=0;
						}
					}
				}
			}
		}
	for(int i = n-1;i>=0;--i){
		for(int j = 0;j<2;++j){
			for(int l = 0;l<4;++l){
				for(int r = 0;r<4;++r){
					for(int k=0;k<4;++k){
						for(int z = 0;z<4;++z){
							set<int>st;
							int last11=l,last12=r,last21=k,last22=z;
							if(j==0){
								if(l)st.insert(l);
								if(r)st.insert(r);
								last12=l;
								last11=mp[s[i]];
							}
							else{
								if(k)st.insert(k);
								if(z)st.insert(z);
								last22=k;
								last21=mp[s[i]];
							}
							st.insert(mp[s[i]]);
							table[j][l][r][k][z][i]=st.size()+max(table[1][last11][last12][last21][last22][i+1], table[0][last11][last12][last21][last22][i+1]);
						}
					}
				}
			}
		}
	}
	cout << max(table[0][0][0][0][0][0],table[1][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: 0 / 8
• Subtask 12: 0 / 8