oj.uz

Submission #660483

# Submission time Handle Problem Language Result Execution time Memory
660483 2022-11-22T01:40:56 Z Blobo2_Blobo2 Miners (IOI07_miners) C++17
100 / 100
 39 ms 852 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
I love my mama
*/
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loop")*/

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2 ios_base::sync_with_stdio(false);cin.tie(0);
#define FR(i, a, b) for(int i=(a); i<(b); i++)
#define FOR(i, n) FR(i, 0, n) 
#define RF(i, a, b) for(int i=(a); i>=(b); i--)

const int mo=998244353;
inline int nxt(){int x;cin>>x;return x;}
int arr[100000],n;
int dp[2][4][4][4];
bool freq[4];

inline int val(int x,int y,int z){
	memset(freq,0,sizeof freq);
	freq[x]=1;
	freq[y]=1;
	freq[z]=1;
	int cnt = 3;
	for(int i=1;i<=3;i++)if(freq[i] == 0)cnt--;
	return cnt;
}

inline void testCase(){
	n=nxt();
	string s;
	cin>>s;
	memset(dp,-1,sizeof dp);
	FOR(i,n){
		if(s[i] == 'M')arr[i] = 1;
		if(s[i] == 'F')arr[i] = 2;
		if(s[i] == 'B')arr[i] = 3;
	}
	int idx = 0;
	RF(i,n-1,0){
		FOR(a,4){
			FOR(b,4){
				FOR(c,4){
					dp[idx][a][b][c] = max(val(arr[i], arr[i-1], a) + dp[idx^1][arr[i-1]][b][c],
	                					   val(arr[i], b, c) + dp[idx^1][b][arr[i-1]][a]);
				}
			}	
		}
		idx^=1;
	}
	idx^=1;
	cout<<dp[idx][0][0][0]+1<<endl;
	return;
}

signed main(){
    Blobo2
    int qu=1;
    while(qu--){
		testCase();
    }
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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