Submission #797810

#	Time	Username	Problem	Language	Result	Execution time	Memory
797810		asdfgrace	Miners (IOI07_miners)	C++17	100 / 100	98 ms	100764 KiB

miners

#include <bits/stdc++.h>
using namespace std;

int dp[100005][4][4][4][4];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  string s; cin >> s;
  memset(dp, -1, sizeof(dp));
  dp[0][3][3][3][3] = 0;
  for (int i = 0; i < n; ++i) {
    for (int a1 = 0; a1 < 4; ++a1) {
      for (int a2 = 0; a2 < 4; ++a2) {
        for (int b1 = 0; b1 < 4; ++b1) {
          for (int b2 = 0; b2 < 4; ++b2) {
            if (dp[i][a1][a2][b1][b2] < 0) continue;
            int cur = (s[i] == 'M' ? 0 : (s[i] == 'F' ? 1 : 2));
            int amask = (((1 << cur) | (1 << a1)) | (1 << a2));
            if (amask >= 8) amask -= 8;
            int acnt = __builtin_popcount(amask);
            int bmask = (((1 << cur) | (1 << b1)) | (1 << b2));
            if (bmask >= 8) bmask -= 8;
            int bcnt = __builtin_popcount(bmask);
            dp[i + 1][a2][cur][b1][b2] = max(dp[i + 1][a2][cur][b1][b2],
              dp[i][a1][a2][b1][b2] + acnt);
            dp[i + 1][a1][a2][b2][cur] = max(dp[i + 1][a1][a2][b2][cur],
              dp[i][a1][a2][b1][b2] + bcnt);
          }
        }
      }
    }
  }
  int ans = 0;
  for (int a1 = 0; a1 < 4; ++a1) {
    for (int a2 = 0; a2 < 4; ++a2) {
      for (int b1 = 0; b1 < 4; ++b1) {
        for (int b2 = 0; b2 < 4; ++b2) {
          ans = max(ans, dp[n][a1][a2][b1][b2]);
        }
      }
    }
  }
  cout << ans << '\n';
}

• 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