oj.uz

Submission #955123

# Submission time Handle Problem Language Result Execution time Memory
955123 2024-03-29T12:24:01 Z stefanneagu Miners (IOI07_miners) C++17
100 / 100
 633 ms 100692 KB 
#include <iostream>
#include <map>
using namespace std;

const int nmax = 1e5 + 1;

int dp[nmax][4][4][4][4];

int main() {
  int n;
  cin >> n;
  string v;
  cin >> v;
  for(auto &it : v) {
    if(it == 'B') {
      it = 1;
    } else if(it == 'F') {
      it = 2;
    } else {
      it = 3;
    }
  }
  for(int i = 0; i <= n; i++) {
    for(int a1 = 0; a1 < 4; a1++) {
      for(int a2 = 0; a2 < 4; a2++) {
        for(int b1 = 0; b1 < 4; b1++) {
          for(int b2 = 0; b2 < 4; b2++) {
            dp[i][a1][a2][b1][b2] = -1;
          }
        }
      }
    }
  }
  v = "$" + v;
  dp[0][0][0][0][0] = 0; // mai trebuie sa pun dat fiind ca era deja 0? nu lol
  int maxx = 0;
  for(int i = 1; i <= n; i++) {
    for(int a1 = 0; a1 < 4; a1++) {
      for(int a2 = 0; a2 < 4; a2++) {
        for(int b1 = 0; b1 < 4; b1++) {
          for(int b2 = 0; b2 < 4; b2++) {
            if(dp[i - 1][a1][a2][b1][b2] == -1) {
              continue;
            }
            // cout << "kek";
            int ia1 = a1, ia2 = a2, ib1 = b1, ib2 = b2;
            if(a1 == 0) {
              a1 = v[i];
            }
            if(a2 == 0) {
              a2 = v[i];
            }
            if(b1 == 0) {
              b1 = v[i];
            }
            if(b2 == 0) {
              b2 = v[i];
            }
            // merge la primu
            map<int, int> fa;
            fa[a1], fa[a2], fa[v[i]];
            // cout << "\nlol:" << a1 << " " << a2 << " " << (int)v[i] << ": " << fa.size() << '\n';
            dp[i][ia2][v[i]][ib1][ib2] = max(dp[i][ia2][v[i]][ib1][ib2], int(dp[i - 1][ia1][ia2][ib1][ib2] + fa.size()));
            // la secund
            map<int, int> fb;
            fb[b1], fb[b2], fb[v[i]];
            dp[i][ia1][ia2][ib2][v[i]] = max(dp[i][ia1][ia2][ib2][v[i]], int(dp[i - 1][ia1][ia2][ib1][ib2] + fb.size()));
            maxx = max(maxx, dp[i][ia1][ia2][ib2][v[i]]);
            maxx = max(maxx, dp[i][ia2][v[i]][ib1][ib2]);
            //if(dp[i - 1][ia1][ia2][ib1][ib2])
            //  cout << i - 1 << " " << ia1 << " " << ia2 << " " << ib1 << " " << ib2 << ": " << dp[i - 1][ia1][ia2][ib1][ib2] << '\n';
            a1 = ia1;
            a2 = ia2;
            b1 = ib1;
            b2 = ib2;
          }
        }
      }
    }
  }
  cout << maxx;
  return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:63:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |             dp[i][ia2][v[i]][ib1][ib2] = max(dp[i][ia2][v[i]][ib1][ib2], int(dp[i - 1][ia1][ia2][ib1][ib2] + fa.size()));
      |                            ^
miners.cpp:63:61: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |             dp[i][ia2][v[i]][ib1][ib2] = max(dp[i][ia2][v[i]][ib1][ib2], int(dp[i - 1][ia1][ia2][ib1][ib2] + fa.size()));
      |                                                             ^
miners.cpp:67:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |             dp[i][ia1][ia2][ib2][v[i]] = max(dp[i][ia1][ia2][ib2][v[i]], int(dp[i - 1][ia1][ia2][ib1][ib2] + fb.size()));
      |                                      ^
miners.cpp:67:71: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |             dp[i][ia1][ia2][ib2][v[i]] = max(dp[i][ia1][ia2][ib2][v[i]], int(dp[i - 1][ia1][ia2][ib1][ib2] + fb.size()));
      |                                                                       ^
miners.cpp:68:55: warning: array subscript has type 'char' [-Wchar-subscripts]
   68 |             maxx = max(maxx, dp[i][ia1][ia2][ib2][v[i]]);
      |                                                       ^
miners.cpp:69:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   69 |             maxx = max(maxx, dp[i][ia2][v[i]][ib1][ib2]);
      |                                             ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2652 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6788 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10844 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 27348 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 76776 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 100692 KB Output is correct