oj.uz

Submission #70384

# Submission time Handle Problem Language Result Execution time Memory
70384 2018-08-22T18:29:30 Z doowey Miners (IOI07_miners) C++14
100 / 100
 210 ms 100968 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 100668 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 100748 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 100748 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 100756 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 100780 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 100780 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 100780 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 100836 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 100860 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 100968 KB Output is correct