oj.uz

Submission #532369

# Submission time Handle Problem Language Result Execution time Memory
532369 2022-03-02T19:03:41 Z Alex_tz307 Miners (IOI07_miners) C++17
100 / 100
 89 ms 588 KB 
#include <bits/stdc++.h>

using namespace std;

int dp[4][4][4][4], newDp[4][4][4][4];
bitset<3> ap;

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void testCase() {
  int n;
  string s;
  cin >> n >> s;
  for (int a = 0; a < 4; ++a) {
    for (int b = 0; b < 4; ++b) {
      for (int c = 0; c < 4; ++c) {
        for (int d = 0; d < 4; ++d) {
          newDp[a][b][c][d] = -1;
        }
      }
    }
  }
  newDp[0][0][0][0] = 0;
  for (char ch : s) {
    int nxt = 1;
    if (ch == 'F') {
      nxt = 2;
    }
    if (ch == 'B') {
      nxt = 3;
    }
    for (int a = 0; a < 4; ++a) {
      for (int b = 0; b < 4; ++b) {
        for (int c = 0; c < 4; ++c) {
          for (int d = 0; d < 4; ++d) {
            dp[a][b][c][d] = newDp[a][b][c][d];
            newDp[a][b][c][d] = -1;
          }
        }
      }
    }
    for (int a = 0; a < 4; ++a) {
      for (int b = 0; b < 4; ++b) {
        for (int c = 0; c < 4; ++c) {
          for (int d = 0; d < 4; ++d) {
            if (dp[a][b][c][d] != -1) {
              ap[0] = ap[1] = ap[2] = false;
              if (a) {
                ap[a - 1] = true;
              }
              if (b) {
                ap[b - 1] = true;
              }
              ap[nxt - 1] = true;
              maxSelf(newDp[b][nxt][c][d], dp[a][b][c][d] + ap.count());
              ap[0] = ap[1] = ap[2] = false;
              if (c) {
                ap[c - 1] = true;
              }
              if (d) {
                ap[d - 1] = true;
              }
              ap[nxt - 1] = true;
              maxSelf(newDp[a][b][d][nxt], dp[a][b][c][d] + ap.count());
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int a = 0; a < 4; ++a) {
    for (int b = 0; b < 4; ++b) {
      for (int c = 0; c < 4; ++c) {
        for (int d = 0; d < 4; ++d) {
          maxSelf(ans, newDp[a][b][c][d]);
        }
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 204 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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