Submission #449829

#	Time	Username	Problem	Language	Result	Execution time	Memory
449829		joshjms	Miners (IOI07_miners)	C++14	100 / 100	145 ms	504 KiB

miners

#include <bits/stdc++.h>
 
#define KON using
#define AQUA namespace std;
 
KON AQUA
 
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define debug(x) cout << #x << " => " << x << "\n";
#define sp " "
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
const int inf = 0x3f3f3f3f;
const int INFF = 1e18 + 5;
const int INF = 1e10 + 5;
const int MX = 3e5 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-5;

int n;
string s;

void solve(){
	cin >> n >> s;

	int dp[2][4][4][4][4];
	memset(dp, -1, sizeof(dp));

	dp[0][0][0][0][0] = 0;

	for(int i = 0; i < n; i++){
		for(int j = 0; j <= 3; j++){
			for(int k = 0; k <= 3; k++){
				for(int l = 0; l <= 3; l++){
					for(int m = 0; m <= 3; m++){
						if(dp[i % 2][j][k][l][m] == -1) continue;

						int next = (s[i] == 'M' ? 1 : s[i] == 'F' ? 2 : 3);

						int p1 = 1 + (j && j != next ? 1 : 0) + (k && k != j && k != next ? 1 : 0);
						dp[(i + 1) % 2][next][j][l][m] = max(dp[(i + 1) % 2][next][j][l][m], dp[i % 2][j][k][l][m] + p1);

						int p2 = 1 + (l && l != next ? 1 : 0) + (m && m != l && m != next ? 1 : 0);
						dp[(i + 1) % 2][j][k][next][l] = max(dp[(i + 1) % 2][j][k][next][l], dp[i % 2][j][k][l][m] + p2);
					}
				}
			}
		}
	}
	int ans = 0;
	for(int j = 0; j <= 3; j++){
		for(int k = 0; k <= 3; k++){
			for(int l = 0; l <= 3; l++){
				for(int m = 0; m <= 3; m++){
					ans = max(ans, dp[n % 2][j][k][l][m]);
				}
			}
		}
	}
	cout << ans << "\n";
}

int32_t main(){
	INIT;
	solve();
}

• 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