oj.uz

Submission #534776

# Submission time Handle Problem Language Result Execution time Memory
534776 2022-03-09T00:11:21 Z devariaota Miners (IOI07_miners) C++17
100 / 100
 986 ms 145512 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int n, a[N], dp[N][4][4][4][4];

// max(mine 1, mine 2)
int rek(int pos, int p1, int p2, int p1_, int p2_){ 
  if(dp[pos][p1][p2][p1_][p2_] != -1) return dp[pos][p1][p2][p1_][p2_];
  set<int> _1, _2;
  if(p1 > 0)
    _1.insert(p1);
  if(p2 > 0)
    _1.insert(p2);
  _1.insert(a[pos]);
  if(p1_ > 0)
    _2.insert(p1_);
  if(p2_ > 0)
    _2.insert(p2_);
  _2.insert(a[pos]);
  int a1 = _1.size(), a2 = _2.size();
  if(pos == n - 1)
  {
    return max(a1,a2);
  }
  // cout << pos <<' '<<p1<<' '<<p2<<' '<<p1_<<' '<<p2_<< " " << a1 << " " << a2 << ": " << a[pos] << '\n';
  return dp[pos][p1][p2][p1_][p2_]=max(rek(pos+1,p2,a[pos],p1_,p2_)+a1,rek(pos+1,p1,p2,p2_,a[pos])+a2);
}

int main(){
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  for(int i=0;i<N;i++)
    for(int j=0;j<4;j++)
      for(int k=0;k<4;k++)
        for(int p=0;p<4;p++)
          for(int r=0;r<4;r++)
          dp[i][j][k][p][r] = -1;
  cin >> n;
  for(int i=0;i<n;i++)
  {
    char c;
    cin >> c;
    if(c == 'M') { 
      a[i] = 1;
    }
    else if(c == 'B') {
      a[i] = 2;
    }
    else {
      a[i] = 3;
    }
  }
  cout << rek(0,0,0,0,0);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100420 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100396 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 100480 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100392 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100420 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 100416 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 100972 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 105024 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 110916 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 128604 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 145512 KB Output is correct