oj.uz

Submission #739587

# Submission time Handle Problem Language Result Execution time Memory
739587 2023-05-10T17:36:25 Z Toxtaq Miners (IOI07_miners) C++17
100 / 100
 1170 ms 401380 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4252 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20308 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 40404 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 100568 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 301168 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1170 ms 401380 KB Output is correct