oj.uz

Submission #70381

# Submission time Handle Problem Language Result Execution time Memory
70381 2018-08-22T18:21:48 Z doowey Miners (IOI07_miners) C++14
76 / 100
 1500 ms 101252 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 calc(int a, int b, int c){
  vector<int> t;
  if(a != 0)t.push_back(a);
  if(b != 0)t.push_back(b);
  if(c != 0)t.push_back(c);
  sort(t.begin(), t.end());
  int eq = 0;
  for(int i = 1;i < t.size(); i ++ ){
    if(t[i] == t[i - 1])
      eq ++;
  }
  return (int)t.size() - eq;
}

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]);
          }
        }
      }
    }
    // 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]);
          }
        }
      }
    }
  }
  cout << ans << " "; 
  return 0;
}

Compilation message

miners.cpp: In function 'int calc(int, int, int)':
miners.cpp:30:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1;i < t.size(); i ++ ){
                 ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 100644 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 100716 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 100944 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 100944 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 100952 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 100964 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 100980 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1580 ms 101132 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 101184 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 101252 KB Time limit exceeded