oj.uz

Submission #220101

# Submission time Handle Problem Language Result Execution time Memory
220101 2020-04-07T02:53:44 Z MODDI Miners (IOI07_miners) C++14
100 / 100
 234 ms 1072 KB 
	#include <bits/stdc++.h>
	using namespace std;
	#define rep(i,n) for(int i=0;i<n;i++)
	template<class T>void chmax(T &a,T b){if(a<b)a=b;}
	template<class T>void chmin(T &a,T b){if(a>b)a=b;}
	constexpr int INF=1000000000;
	int main(){
	    int n,a[100010],dp[2][4][4][4][4];
	    string s;
	    cin>>n>>s;
	    rep(i,2){
	        rep(c,4){
	            rep(d,4){
	                rep(e,4){
	                    rep(f,4){
	                        dp[i][c][d][e][f]=-INF;
	                    }
	                }
	            }
	        }
	    }
	    dp[0][3][3][3][3]=0;
	    rep(i,n){
	        if(s[i]=='M')a[i]=0;
	        if(s[i]=='F')a[i]=1;
	        if(s[i]=='B')a[i]=2;
	    }
	    rep(i,n){
	        rep(c,4){
	            rep(d,4){
	                if(c==3&&d!=3)continue;
	                rep(e,4){
	                    rep(f,4){
	                        int x[4]={0,0,0,0},y[4]={0,0,0,0};
	                        x[c]++,x[d]++,x[a[i]]++;
	                        y[e]++,y[f]++,y[a[i]]++;
	                        int X=0,Y=0;
	                        rep(i,3){
	                            X+=(bool)x[i];
	                            Y+=(bool)y[i];
	                        }
	                        chmax(dp[(i+1)%2][a[i]][c][e][f],dp[i%2][c][d][e][f]+X);
	                        chmax(dp[(i+1)%2][c][d][a[i]][e],dp[i%2][c][d][e][f]+Y);
	                    }
	                }
	            }
	        }
	    }
	    int ans=0;
	    rep(c,4){
	        rep(d,4){
	            if(c==3&&d!=3)continue;
	            rep(e,4){
	                rep(f,4){
	                    if(e==3&&f!=3)continue;
	                    chmax(ans,dp[n%2][c][d][e][f]);
	                }
	            }
	        }
	    }
	    cout<<ans<<endl;
	    return 0;
	}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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