oj.uz

Submission #797810

# Submission time Handle Problem Language Result Execution time Memory
797810 2023-07-29T23:56:40 Z asdfgrace Miners (IOI07_miners) C++17
100 / 100
 98 ms 100764 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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