oj.uz

Submission #411915

# Submission time Handle Problem Language Result Execution time Memory
411915 2021-05-26T08:49:09 Z Karliver Miners (IOI07_miners) C++14
100 / 100
 367 ms 604 KB 
	
 #include <bits/stdc++.h>
 
 #define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
 #define all(v) (v).begin(), (v).end()
 using namespace  std;
 #define forn(i,n) for (int i = 0; i < (n); ++i)
 #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
 using ll = long long;
 int mod = (ll)1e9 + 7;
 #define PI acos(-1)
 typedef pair<int, int> pairs;
 
 const int INF = 1e9 + 1;
 const int N = 2e5 + 100;
 const double eps = 1e-7;
 
 template <class T> using V = vector<T>;  // from yosupo 
 template <class T> using VV = V<V<T>>;  // from yosupo
 
 template <typename XPAX>
 void ckma(XPAX &x, XPAX y) {
     x = (x < y ? y : x);
 }
 template <typename XPAX>
 void ckmi(XPAX &x, XPAX y) {
     x = (x > y ? y : x);
 }
 
 void solve() {
 
 
 	int n;
 	cin >> n;
 	string s;
 	cin >> s;
 	
 	map<char, int> G;
 	G['M'] = 0;
 	G['F'] = 1;

 	G['B'] = 2;

 	int dp[2][4][4][4][4];

 	auto calc = [&](int a, int b, int c) {
 		V<int> cnt(4, 0);
 		cnt[a]++;
 		cnt[b]++;
 		cnt[c]++;
 		int ans= 0;
 		forn(i, 3)ans += (cnt[i] > 0);
 		return ans;
 	};

 	memset(dp, -1, sizeof(dp));
 	dp[0][3][3][3][3] = 0;
 	forn(i, n) {
 		int x = G[s[i]];
 		memset(dp[1], -1, sizeof(dp[1]));
 		forn(a, 4) forn(b, 4) forn(c, 4) forn(d, 4) {
 			if(dp[0][a][b][c][d] == -1)continue;

 			ckma(dp[1][b][x][c][d], dp[0][a][b][c][d] + calc(a, b, x));
 			ckma(dp[1][a][b][d][x], dp[0][a][b][c][d] + calc(c, d, x));
 		}
 		swap(dp[0], dp[1]);
 	}
 	int ans = 0;

 	forn(a, 4) forn(b, 4) forn(c, 4) forn(d, 4) ckma(ans, dp[0][a][b][c][d]);
 	cout << ans << '\n';

 
 
 }
 void test_case() {
     int t;
     cin >> t;
     forn(p, t) {
 
         //cout << "Case #" << p + 1 << ": ";
         solve();
     }
 }
 int main() {
 
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
 
     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 204 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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