제출 #235573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235573		Haunted_Cpp	Miners (IOI07_miners)	C++17	100 / 100	217 ms	109048 KiB

miners

/**
 *  author: Duarte Nobrega
 *  created: 28.05.2020    
**/

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

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

const int N = 1e5 + 5;

int dp [N][4][4][4][4];
int food [N];

int n, mask;
string w;

int calc (int a, int b, int c) {
  mask = 0;
  mask |= (1 << a);
  mask |= (1 << b);
  mask |= (1 << c);
  return __builtin_popcount(mask) - (mask & 1);
}

int solve (int p = 0, int l1 = 0, int l2 = 0, int r1 = 0, int r2 = 0) {
  if (p >= n) return 0;
  int &res = dp[p][l1][l2][r1][r2];
  if (~res) return res;
  res = 0;
  // Place left
  res = max (res, solve (p + 1, food[p], l1, r1, r2) + calc (l1, l2, food[p])); 
  // Place right
  res = max (res, solve (p + 1, l1, l2, food[p], r1) + calc (r1, r2, food[p])); 
  return res;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  memset (dp, -1, sizeof(dp));
  cin >> n >> w;
  for (int i = 0; i < n; i++) {
    if (w[i] == 'M') food[i] = 1;
    else if (w[i] == 'F') food[i] = 2;
    else food[i] = 3;
  }
  cout << solve () << '\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