Submission #955123

#	Time	Username	Problem	Language	Result	Execution time	Memory
955123		stefanneagu	Miners (IOI07_miners)	C++17	100 / 100	633 ms	100692 KiB

miners

#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 (stderr)

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 / 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