oj.uz

Submission #449829

# Submission time Handle Problem Language Result Execution time Memory
449829 2021-08-02T08:28:14 Z joshjms Miners (IOI07_miners) C++14
100 / 100
 145 ms 504 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 316 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 332 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 356 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 460 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 504 KB Output is correct