제출 #1196633

#제출 시각아이디문제언어결과실행 시간메모리
1196633julia_08Miners (IOI07_miners)C++20
100 / 100
140 ms101028 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int a[MAXN];

int dp[MAXN][4][4][4][4];

int cnt(int x, int y, int z){
  bool zero = (x == 0 || y == 0 || z == 0);
  if(x == y && y == z) return 1 - zero;
  if(x == y || x == z || y == z) return 2 - zero;
  return 3 - zero;
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  for(int i=1; i<=n; i++){

    char c; cin >> c;

    if(c == 'M') a[i] = 1;
    if(c == 'F') a[i] = 2;
    if(c == 'B') a[i] = 3;

  }

  for(int i=0; i<n; i++){
    for(int x1=0; x1<4; x1++){
      for(int y1=0; y1<4; y1++){
        for(int x2=0; x2<4; x2++){
          for(int y2=0; y2<4; y2++){
            dp[i][x1][y1][x2][y2] = -1e9;
          }
        }
      }
    }
  }

  dp[0][0][0][0][0] = 0;

  for(int i=0; i<n; i++){

    for(int x1=0; x1<4; x1++){
      for(int y1=0; y1<4; y1++){

        for(int x2=0; x2<4; x2++){
          for(int y2=0; y2<4; y2++){

            dp[i + 1][y1][a[i + 1]][x2][y2] = max(
              dp[i + 1][y1][a[i + 1]][x2][y2],
              dp[i][x1][y1][x2][y2] + cnt(x1, y1, a[i + 1])
            );

            dp[i + 1][x1][y1][y2][a[i + 1]] = max(
              dp[i + 1][x1][y1][y2][a[i + 1]],
              dp[i][x1][y1][x2][y2] + cnt(x2, y2, a[i + 1])
            );

          }
        }

      }
    }

  }

  int ans = 0;

  for(int x1=0; x1<4; x1++){
    for(int y1=0; y1<4; y1++){
      for(int x2=0; x2<4; x2++){
        for(int y2=0; y2<4; y2++){
          ans = max(ans, dp[n][x1][y1][x2][y2]);
        }
      }
    }
  }

  cout << ans << "\n";

  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...