oj.uz

Submission #235575

# Submission time Handle Problem Language Result Execution time Memory
235575 2020-05-28T15:42:31 Z Haunted_Cpp Miners (IOI07_miners) C++17
100 / 100
 214 ms 108956 KB 
/**
 *  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);
  mask &= ~1;
  return __builtin_popcount(mask);
}

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100472 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100472 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100472 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 100476 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 100648 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 100600 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 100984 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 101432 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 102688 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 106940 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 108956 KB Output is correct