Submission #532369

#	Time	Username	Problem	Language	Result	Execution time	Memory
532369		Alex_tz307	Miners (IOI07_miners)	C++17	100 / 100	89 ms	588 KiB

miners

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