Submission #988328

#	Time	Username	Problem	Language	Result	Execution time	Memory
988328		huutuan	Miners (IOI07_miners)	C++14	100 / 100	59 ms	100952 KiB

miners

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;
int n, f[N][16][16], a[N];
pair<int, int> nxt[16][4];

void maximize(int &x, int y){
   x=max(x, y);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i){
      char c; cin >> c;
      a[i]=string("?MFB").find(c);
   }
   for (int i=0; i<16; ++i) for (int j=1; j<4; ++j){
      set<int> st;
      st.insert(i%4); st.insert(i/4); st.insert(j);
      st.erase(0);
      nxt[i][j]={st.size(), (i%4)*4+j};
   }
   memset(f, -1, sizeof f);
   f[0][0][0]=0;
   for (int i=0; i<n; ++i){
      for (int j=0; j<16; ++j) for (int k=0; k<16; ++k) if (f[i][j][k]!=-1){
         maximize(f[i+1][nxt[j][a[i+1]].second][k], f[i][j][k]+nxt[j][a[i+1]].first);
         maximize(f[i+1][j][nxt[k][a[i+1]].second], f[i][j][k]+nxt[k][a[i+1]].first);
      }
   }
   int ans=-1;
   for (int i=0; i<16; ++i) for (int j=0; j<16; ++j) ans=max(ans, f[n][i][j]);
   cout << ans << '\n';
   return 0;
}

• 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