제출 #167401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167401		Nightlight	Miners (IOI07_miners)	C++14	100 / 100	527 ms	298716 KiB

miners

#include <bits/stdc++.h>
using namespace std;
 
int diff[3][3][3];
int memo[100005][3][3][3][3][3][3];
int food[100005];
int N;
 
int CD(int a, int b, int c){map<int,int>  M;M[a]++;M[b]++;M[c]++;return M.size();}
 
int dp(int id, int A1, int B1, int A2, int B2, int S1, int S2){
  if(id >= N)return 0;
  if(memo[id][A1][B1][A2][B2][S1][S2] != -1)return memo[id][A1][B1][A2][B2][S1][S2];
  //give to 1
  int G1;
  if(S1 == 2){
    G1 = diff[A1][B1][food[id]] + dp(id+1, food[id], A1, A2, B2, S1, S2);
  }else if(S1 == 1){
    G1 = (A1 == food[id] ? 0 : 1) + 1 + dp(id+1, food[id], A1, A2, B2, S1+1, S2);
  }else G1 = 1 + dp(id+1, food[id], A1, A2, B2, S1+1, S2);
  //give to 2
  int G2;
  if(S2 == 2){
    G2 = diff[A2][B2][food[id]] + dp(id+1, A1, B1, food[id], A2, S1, S2);
  }else if(S2 == 1){
    G2 = (A2 == food[id] ? 0 : 1) + 1 + dp(id+1, A1, B1, food[id], A2, S1, S2+1);
  }else G2 = 1 + dp(id+1, A1, B1, food[id], A2, S1, S2+1);
  return memo[id][A1][B1][A2][B2][S1][S2] = max(G1, G2);
}
 
int main() {
  memset(memo, -1, sizeof(memo));
  cin >> N;
  char tmp;
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
      for(int k = 0; k < 3; k++)
        diff[i][j][k] = CD(i, j, k);
  for(int i = 0; i < N; i++){
    cin >> tmp;
    if(tmp == 'M')food[i] = 0;
    else if(tmp == 'B')food[i] = 1;
    else food[i] = 2;
  }
  cout << dp(0, 0, 0, 0, 0, 0, 0) << "\n";
}

• 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