Submission #660479

#	Time	Username	Problem	Language	Result	Execution time	Memory
660479		Blobo2_Blobo2	Miners (IOI07_miners)	C++17	100 / 100	188 ms	110540 KiB

miners

/*
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);

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

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=0;i<3;i++)if(freq[i] == 0)cnt--;
	return cnt;
}

int solve(int idx = 0,int x1 = 3,int y1 = 3,
		  			  int x2 = 3,int y2 = 3){
	if(idx == n)return 0;
	int &ret = dp[idx][x1][y1][x2][y2];
	if(~ret)return ret;
	return ret = max(val(arr[idx],x1,y1) + solve(idx+1, arr[idx], x1, x2, y2),
					 val(arr[idx],x2,y2) + solve(idx+1, x1, y1, arr[idx], x2));
}

void testCase(){
	n=nxt();
	string s;
	cin>>s;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<n;i++){
		if(s[i] == 'M')arr[i] = 0;
		if(s[i] == 'F')arr[i] = 1;
		if(s[i] == 'B')arr[i] = 2;
	}
	cout<<solve()<<endl;
	return;
}

signed main(){
    Blobo2
    int qu=1;
    while(qu--){
		testCase();
    }
    return 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