Submission #739587

#	Time	Username	Problem	Language	Result	Execution time	Memory
739587		Toxtaq	Miners (IOI07_miners)	C++17	100 / 100	1170 ms	401380 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;
                    }
                }
            }
        }
    }
    vector<int>tempo(4);
	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){
							int last11=l,last12=r,last21=k,last22=z, cnt = 0;
							if(j==0){
								if(l){
                                    if(!tempo[l])cnt++;
                                    tempo[l]++;
								}
								if(r){
                                    if(!tempo[r])cnt++;
                                    tempo[r]++;
								}
								last12=l;
								last11=mp[s[i]];
							}
							else{
								if(k){
                                    if(!tempo[k])cnt++;
                                    tempo[k]++;
								}
								if(z){
                                    if(!tempo[z])cnt++;
                                    tempo[z]++;
								}
								last22=k;
								last21=mp[s[i]];
							}
							if(!tempo[mp[s[i]]])cnt++;
							for(int i = 0;i < 4;++i)tempo[i] = 0;
							table[j][l][r][k][z][i]=cnt+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: 8 / 8
• Subtask 12: 8 / 8