Submission #989668

#	Time	Username	Problem	Language	Result	Execution time	Memory
989668		aaaaaarroz	Miners (IOI07_miners)	C++17	100 / 100	498 ms	100696 KiB

miners

#include <bits/stdc++.h>
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; 
  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;
            }
            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];
            }
            map<int, int> fa;
            fa[a1], fa[a2], fa[v[i]];
            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()));
            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]);
            a1 = ia1;
            a2 = ia2;
            b1 = ib1;
            b2 = ib2;
          }
        }
      }
    }
  }
  cout << maxx;
  return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:59:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |             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:59:61: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |             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:62:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |             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:62:71: warning: array subscript has type 'char' [-Wchar-subscripts]
   62 |             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:63:55: warning: array subscript has type 'char' [-Wchar-subscripts]
   63 |             maxx = max(maxx, dp[i][ia1][ia2][ib2][v[i]]);
      |                                                       ^
miners.cpp:64:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   64 |             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