Submission #1325785

#TimeUsernameProblemLanguageResultExecution timeMemory
1325785SonicMLMiners (IOI07_miners)C++20
100 / 100
120 ms396 KiB
#include <iostream>

using namespace std;

int const INF = 1e9+7;

int dp[2][4][4][4][4]; 

int add(int a, int b, int c) {
  int freq[4];
  freq[0] = freq[1] = freq[2] = freq[3] = 0;
  freq[a]++;
  freq[b]++;
  freq[c]++;
  int ans = min(1, freq[1]) + min(1, freq[2]) + min(1, freq[3]);
  return ans;
}

int main() {

  int n;
  cin >> n;
  for(int a1 = 0;a1 <= 3;a1++) {
    for(int a2 = 0;a2 <= 3;a2++) {
      for(int b1 = 0;b1 <= 3;b1++) {
        for(int b2 = 0;b2 <= 3;b2++) {
          dp[0][a1][a2][b1][b2] = -INF;
          dp[1][a1][a2][b1][b2] = -INF;
        }
      }
    } 
  }
  dp[0][0][0][0][0] = 0;
  for(int i = 1;i <= n;i++) {
    char ch;
    int type = 0;
    cin >> ch;
    if(ch == 'M') {
      type = 1;
    }else if(ch == 'F') {
      type = 2;
    }else if(ch == 'B') {
      type = 3;
    }
    for(int a1 = 0;a1 <= 3;a1++) {
      for(int a2 = 0;a2 <= 3;a2++) {
        for(int b1 = 0;b1 <= 3;b1++) {
          for(int b2 = 0;b2 <= 3;b2++) {
            dp[1][type][a1][b1][b2] = max(dp[1][type][a1][b1][b2], dp[0][a1][a2][b1][b2] + add(a1, a2, type));   
            dp[1][a1][a2][type][b1] = max(dp[1][a1][a2][type][b1], dp[0][a1][a2][b1][b2] + add(b1, b2, type));
          }
        }
      }
    }
    for(int a1 = 0;a1 <= 3;a1++) {
      for(int a2 = 0;a2 <= 3;a2++) {
        for(int b1 = 0;b1 <= 3;b1++) {
          for(int b2 = 0;b2 <= 3;b2++) {
            dp[0][a1][a2][b1][b2] = dp[1][a1][a2][b1][b2];
            dp[1][a1][a2][b1][b2] = -INF;
          }
        }
      }
    }
  }
  int ans = 0;
  for(int a1 = 0;a1 <= 3;a1++) {
    for(int a2 = 0;a2 <= 3;a2++) {
      for(int b1 = 0;b1 <= 3;b1++) {
        for(int b2 = 0;b2 <= 3;b2++) {
          ans = max(ans, dp[0][a1][a2][b1][b2]);
        }
      }
    }
  } 
  cout << ans;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...