oj.uz

Submission #739386

# Submission time Handle Problem Language Result Execution time Memory
739386 2023-05-10T11:35:10 Z Toxtaq Miners (IOI07_miners) C++17
84 / 100
 1500 ms 401356 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;
						}
					}
				}
			}
		}
	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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 340 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 2 ms 340 KB Output is correct

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 301072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1572 ms 401356 KB Time limit exceeded
2 Halted 0 ms 0 KB -