Submission #70384

#	Time	Username	Problem	Language	Result	Execution time	Memory
70384		doowey	Miners (IOI07_miners)	C++14	100 / 100	210 ms	100968 KiB

miners

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double db;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue

const int N = (int)1e5 + 9;

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

int k;
int calc(int a, int b, int c){
  k = 0;
  if(a != 0)
    k ++ ;
  if(b != 0)
    k ++ ;
  if(c != 0)
    k ++ ;
  if(k == 1)
    return 1;
  if(k == 2)
    return (a != b) + 1;
  if(a == b and b == c)
    return 1;
  else if(a == b or b == c or a == c)
    return 2;
  else 
    return 3;
}

void upd(int &a, int b){
  a = max(a, b);
}

int main(){
  fastIO;
  memset(dp, -10000000, sizeof dp);
  dp[0][0][0][0][0] = 0;
  int n;
  cin >> n;
  char k;
  int y;
  int ans = 0;
  for(int i = 1; i <= n;i ++ ){
    cin >> k;
    if(k == 'M')
      y = 1;
    else if(k == 'F')
      y = 2;
    else
      y = 3;
    // send this to mine 1:
    for(int t1 = 0; t1 < 4; t1 ++ ){
      for(int t2 = 0; t2 < 4; t2 ++ ){
        for(int s1 = 0; s1 < 4; s1 ++ ){
          for(int s2 = 0; s2 < 4; s2 ++ ){
            upd(dp[i][y][t1][s1][s2], dp[i - 1][t1][t2][s1][s2] + calc(y, t1, t2));
            upd(ans, dp[i][y][t1][s1][s2]);
            if(s1 == 0)
              continue;
          }
        }
      }
      if(t1 == 0)
        continue;
    }
    // send this to mine 2:
    for(int t1 = 0; t1 < 4; t1 ++ ){
      for(int t2 = 0; t2 < 4; t2 ++ ){
        for(int s1 = 0; s1 < 4; s1 ++ ){
          for(int s2 = 0; s2 < 4; s2 ++ ){
            upd(dp[i][t1][t2][y][s1], dp[i - 1][t1][t2][s1][s2] + calc(y, s1, s2));
            upd(ans, dp[i][t1][t2][y][s1]);
            if(s1 == 0)
              continue;
          }
        }
      }
      if(t1 == 0)
        continue;
    }
  }
  cout << ans << " "; 
  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