Submission #411915

#	Time	Username	Problem	Language	Result	Execution time	Memory
411915		Karliver	Miners (IOI07_miners)	C++14	100 / 100	367 ms	604 KiB

miners

	
 #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 / 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