Submission #1008105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008105		vjudge1	Miners (IOI07_miners)	C++17	100 / 100	42 ms	32436 KiB

miners

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int dp[MAXN][3][3][3][3];
pii other(int i){
	if (i == 0) return {1, 2};
	if (i == 1) return {0, 2};
	if (i == 2) return {0, 1};
	return {0, 0};
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++){
		char x;
		cin >> x;
		if (x == 'M') a[i] = 0;
		else if (x == 'F') a[i] = 1;
		else if (x == 'B') a[i] = 2;
	}
	memset(dp, -inf, sizeof(dp));
	for (int i = 0; i < 3; i++){
		for (int j = 0; j < 3; j++){
			dp[0][i][i][j][j] = 1;
		}
	}
	debug(a);
	for (int i = 1; i <= n; i++){
		// but in one
		for (int j = 0; j < 3; j++){
			for (int k = 0; k < 3; k++){
				for (int l = 0; l < 3; l++){
					if (a[i] != j) {
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][3 - a[i] - j][j][k][l] + 3); 
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][a[i]][j][k][l] + 2); 
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][j][j][k][l] + 2); 
					} else {
						pii o = other(a[i]);
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][o.F][a[i]][k][l] + 2); 
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][o.S][a[i]][k][l] + 2); 
						ckmax(dp[i][j][a[i]][k][l], dp[i - 1][a[i]][a[i]][k][l] + 1); 
					}
					if (a[i] != l){
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][3 - a[i] - l][l] + 3); 
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][a[i]][l] + 2); 
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][l][l] + 2); 
					} else {
						pii o = other(a[i]);
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][o.F][l] + 2); 
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][o.S][l] + 2); 
						ckmax(dp[i][j][k][l][a[i]], dp[i - 1][j][k][l][l] + 1); 
					}
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				for (int l = 0; l < 3; l++)
					ckmax(ans, dp[n][i][j][k][l]);
	cout << ans - 5 << endl;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
miners.cpp:49:2: note: in expansion of macro 'debug'
   49 |  debug(a);
      |  ^~~~~

• 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