제출 #534776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
534776		devariaota	Miners (IOI07_miners)	C++17	100 / 100	986 ms	145512 KiB

miners

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, a[N], dp[N][4][4][4][4];

// max(mine 1, mine 2)
int rek(int pos, int p1, int p2, int p1_, int p2_){ 
  if(dp[pos][p1][p2][p1_][p2_] != -1) return dp[pos][p1][p2][p1_][p2_];
  set<int> _1, _2;
  if(p1 > 0)
    _1.insert(p1);
  if(p2 > 0)
    _1.insert(p2);
  _1.insert(a[pos]);
  if(p1_ > 0)
    _2.insert(p1_);
  if(p2_ > 0)
    _2.insert(p2_);
  _2.insert(a[pos]);
  int a1 = _1.size(), a2 = _2.size();
  if(pos == n - 1)
  {
    return max(a1,a2);
  }
  // cout << pos <<' '<<p1<<' '<<p2<<' '<<p1_<<' '<<p2_<< " " << a1 << " " << a2 << ": " << a[pos] << '\n';
  return dp[pos][p1][p2][p1_][p2_]=max(rek(pos+1,p2,a[pos],p1_,p2_)+a1,rek(pos+1,p1,p2,p2_,a[pos])+a2);
}

int main(){
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  for(int i=0;i<N;i++)
    for(int j=0;j<4;j++)
      for(int k=0;k<4;k++)
        for(int p=0;p<4;p++)
          for(int r=0;r<4;r++)
          dp[i][j][k][p][r] = -1;
  cin >> n;
  for(int i=0;i<n;i++)
  {
    char c;
    cin >> c;
    if(c == 'M') { 
      a[i] = 1;
    }
    else if(c == 'B') {
      a[i] = 2;
    }
    else {
      a[i] = 3;
    }
  }
  cout << rek(0,0,0,0,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