oj.uz

Submission #449609

# Submission time Handle Problem Language Result Execution time Memory
449609 2021-08-02T07:26:07 Z joshjms Miners (IOI07_miners) C++14
100 / 100
 980 ms 200896 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[n + 1][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][j][k][l][m] == -1) continue;

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

						set <int> s1, s2;

						s1.insert(next);
						if(j) s1.insert(j);
						if(k) s1.insert(k);

						dp[i + 1][next][j][l][m] = max(dp[i + 1][next][j][l][m], dp[i][j][k][l][m] + (int) s1.size());

						s2.insert(next);
						if(l) s2.insert(l);
						if(m) s2.insert(m);
						dp[i + 1][j][k][next][l] = max(dp[i + 1][j][k][next][l], dp[i][j][k][l][m] + (int) s2.size());
					}
				}
			}
		}
	}
	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][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 1 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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