oj.uz

Submission #660479

# Submission time Handle Problem Language Result Execution time Memory
660479 2022-11-22T01:00:01 Z Blobo2_Blobo2 Miners (IOI07_miners) C++17
100 / 100
 188 ms 110540 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);

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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