Submission #1196633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196633		julia_08	Miners (IOI07_miners)	C++20	100 / 100	140 ms	101028 KiB

miners

#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;
}

• 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