Submission #1201878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201878		vicvic	Miners (IOI07_miners)	C++20	In queue	0 ms	0 KiB

miners

#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
const int NMAX=1e5;
int n;
string input;
int v[NMAX+5];
int temp[NMAX+5];
int dp[NMAX+5][4][4][4][4];
int getVal (vector <int> vec)
{
    set <int> setul;
    for (auto chestie : vec)
        if (chestie) setul.insert (chestie);
    return setul.size();
}
int makeDP (int i, int a, int a1, int b, int b1)
{
    if (i==n)
        return 0;
    int &res=dp[i][a][a1][b][b1];
    if (res!=-1)
        return res;
    int rez1=getVal ({a1, a, v[i]});
    int rez2=getVal ({b, b1, v[i]});
    return res=max (rez1+makeDP (i+1, v[i], a, b, b1), rez2+makeDP (i+1, a, a1, v[i], b));
}
int main ()
{
    temp['M']=1;
    temp['B']=2;
    temp['F']=3;
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    cin >> input;
    memset (dp, -1, sizeof(dp));
    for (int i=0;i<n;i++)
    {
        v[i]=temp[input[i]];
    }
    cout << makeDP (0, 0, 0, 0, 0);
    return 0;
}