Submission #343792

#	Time	Username	Problem	Language	Result	Execution time	Memory
343792		anubhavdhar	Miners (IOI07_miners)	C++14	43 / 100	1584 ms	624 KiB

miners

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double

using namespace std;

const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

// dp[i][a][b][c][d] i -> pos; a, b are last two in 1st mine, c, d- > second mine

// 0, 1, 2, 3

int to_int(char c){
	return (c == 'M') ? 1 : ((c == 'F') ? 2 : 3);
}

signed main(){

	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	int N;
	cin>>N;
	string S;
	cin>>S;

	S = '*' + S;

	ll dp[2][4][4][4][4];

	memset(dp, 0, sizeof dp);

	dp[0][0][0][0][0] = 0;
	dp[1][to_int(S[1])][0][0][0] = 1;
	dp[1][0][0][to_int(S[1])][0] = 1;

	int freq[4];
	freq[0] = inf;
	freq[1] = freq[2] = freq[3] = 0;

	freq[to_int(S[1])]++;

	for(int i = 2; i <= N; ++i){
		++freq[to_int(S[i])];
		for(int a = 0; a < 4; ++a){
			for(int b = 0; b < 4; ++b){
				for(int c = 0; c < (b ? 4 : 1); ++c){
					dp[i&1][to_int(S[i])][a][b][c] = 0;
					dp[i&1][b][c][to_int(S[i])][a] = 0;
					for(int d = 0; d < (a ? 4 : 1); ++d){
						if((a == 0 and d != 0) || (b == 0 and c != 0)){
							continue;
							assert(false);
						}
						--freq[a];
						--freq[b];
						--freq[c];
						--freq[d];
						if(min({freq[0], freq[1], freq[2], freq[3]}) < 0){
							++freq[a];
							++freq[b];
							++freq[c];
							++freq[d];
							continue;
						}
						++freq[a];
						++freq[b];
						++freq[c];
						++freq[d];
						set<int> SS;
						for(int x : {a, d, to_int(S[i])}){
							if(x != 0){
								SS.insert(x);
							}
						}
						dp[i&1][to_int(S[i])][a][b][c] = max(dp[(i-1)&1][a][d][b][c] + (ll)SS.size(), dp[i&1][to_int(S[i])][a][b][c]);
						dp[i&1][b][c][to_int(S[i])][a] = max(dp[(i-1)&1][b][c][a][d] + (ll)SS.size(), dp[i&1][b][c][to_int(S[i])][a]);
					}
				}
			}
		}
	}

	// for(int i = 0; i <= N; ++i){
	// 	for(int a = 0; a < 4; ++a){
	// 		for(int b = 0; b < 4; ++b){
	// 			for(int c = 0; c < 4; ++c){
	// 				for(int d = 0; d < 4; ++d){
	// 					cerr<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"] = "<<dp[i][a][b][c][d]<<'\n';
	// 				}
	// 			}
	// 		}
	// 	}
	// }

	ll ans = 0;
	for(int a = 0; a < 4; ++a){
		for(int b = 0; b < 4; ++b){
			for(int c = 0; c < 4; ++c){
				for(int d = 0; d < 4; ++d){
					if((a == 0 and d != 0) || (b == 0 and c != 0)){
						continue;
					}
					ans = max(dp[N&1][a][b][c][d], ans);
				}
			}
		}
	}

	cout<<ans<<'\n';
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 7 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8