Submission #851526

#	Time	Username	Problem	Language	Result	Execution time	Memory
851526		abcvuitunggio	Miners (IOI07_miners)	C++17	100 / 100	644 ms	113848 KiB

miners

#include <bits/stdc++.h>
using namespace std;
int n,a[100001],dp[100001][4][4][4][4];
string s;
set <int> sl,sr;
int f(int i, int j, int k, int l, int m){
    if (i>n)
        return 0;
    if (dp[i][j][k][l][m]!=-1)
        return dp[i][j][k][l][m];
    sl.clear();
    sr.clear();
    if (j)
        sl.insert(j);
    if (k)
        sl.insert(k);
    if (l)
        sr.insert(l);
    if (m)
        sr.insert(m);
    sl.insert(a[i]);
    sr.insert(a[i]);
    int x=sl.size(),y=sr.size();
    return dp[i][j][k][l][m]=max(f(i+1,k,a[i],l,m)+x,f(i+1,j,k,m,a[i])+y);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> s;
    for (int i=1;i<=n;i++)
        a[i]=(s[i-1]=='M'?1:s[i-1]=='F'?2:3);
    memset(dp,-1,sizeof(dp));
    cout << f(1,0,0,0,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