Submission #235572

#	Time	Username	Problem	Language	Result	Execution time	Memory
235572		Haunted_Cpp	Miners (IOI07_miners)	C++17	100 / 100	1277 ms	110772 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];

vector<int> food;

int n;
string w;

set<int> cnt;

int calc (int a, int b, int c) {
  cnt.clear();
  cnt.insert(a);
  cnt.insert(b);
  cnt.insert(c);
  cnt.erase(0);
  return (int) cnt.size();
}

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 (auto to : w) {
    if (to == 'M') food.emplace_back(1);
    else if (to == 'F') food.emplace_back(2);
    else food.emplace_back(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