Submission #1322398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322398		g4yuhg	Miners (IOI07_miners)	C++20	100 / 100	86 ms	101016 KiB

miners

#include<bits/stdc++.h>
//#include "minesweeper.h"
typedef int ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 500005
#define endl '\n'
#define y0 Y0
using namespace std;

const ll inf = 1e9;

ll rand(ll l, ll r) {
	return l + rand() % (r - l + 1);
}

bool ghuy4g;

ll f[100005][4][4][4][4];

ll n, a[N];

ll cal(ll x, ll y, ll z) {
	ll res = 0;
	if (x) res ++ ;
	if (y && y != x) res ++ ;
	if (z && z != y && z != x) res ++ ;
	return res; 
}

void mx(ll &u, ll v) {
	u = max(u, v);
}

void solve() {
	for (int i = 0; i <= n; i ++) {
		for (int j = 0; j <= 3; j ++) {
			for (int z = 0; z <= 3; z ++) {
				for (int u = 0; u <= 3; u ++) {
					for (int v = 0; v <= 3; v ++) {
						f[i][j][z][u][v] = -inf;
					}
				}
			}
		}
	}
	f[0][0][0][0][0] = 0;
	ll ans = 0;
	for (int i = 1; i <= n; i ++) {
		for (int x1 = 0; x1 <= 3; x1 ++) {
			for (int x2 = 0; x2 <= 3; x2 ++) {
				for (int u1 = 0; u1 <= 3; u1 ++) {
					for (int u2 = 0; u2 <= 3; u2 ++) {
						if (f[i - 1][x1][x2][u1][u2] == -inf) continue;
						// dien vao 1
						ll base = f[i - 1][x1][x2][u1][u2];
						mx(f[i][a[i]][x1][u1][u2], base + cal(x1, x2, a[i]));
						mx(f[i][x1][x2][a[i]][u1], base + cal(u1, u2, a[i]));
						ans = max(ans, f[i][a[i]][x1][u1][u2]);
						ans = max(ans, f[i][x1][x2][a[i]][u1]); 
					}
				}
			}
		}
	}
	cout << ans << endl;
}

bool klinh;

signed main() {
	if (fopen("kghmdlod.inp", "r")) {
		freopen("kghmdlod.inp", "r", stdin);
		freopen("kghmdlod.out", "w", stdout);
	}
	srand(time(0));
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> n;
	//n = 1e5;
	for (int i = 1; i <= n; i ++) {
		char u; cin >> u;
		if (u == 'M') a[i] = 1;
		if (u == 'B') a[i] = 2;
		if (u == 'F') a[i] = 3;
		//a[i] = rand(1, 3);
	}
	solve();
	
	cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:74:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |                 freopen("kghmdlod.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
miners.cpp:75:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |                 freopen("kghmdlod.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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