Submission #863258

#	Time	Username	Problem	Language	Result	Execution time	Memory
863258		HuyQuang_re_Zero	Miners (IOI07_miners)	C++14	100 / 100	120 ms	110680 KiB

miners

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 100005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define rand(l,r) (l+rng()%(r-l+1))
using namespace std;
int f[N][4][4][4][4],a[N],i,j,k,n,c[4][4][4];
string s;
int cal(int i,int k1,int k2,int h1,int h2)
{
    if(i>n) return 0;
    if(f[i][k1][k2][h1][h2]>-1) return f[i][k1][k2][h1][h2];
    int res=0;
    res=max(res,cal(i+1,k2,a[i],h1,h2)+c[k1][k2][a[i]]);
    res=max(res,cal(i+1,k1,k2,h2,a[i])+c[h1][h2][a[i]]);
    return f[i][k1][k2][h1][h2]=res;
}
int main()
{
  //  freopen("miners.inp","r",stdin);
  //  freopen("miners.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>s; s=" "+s;
    for(i=1;i<=n;i++)
    {
        if(s[i]=='M') a[i]=1;
        if(s[i]=='F') a[i]=2;
        if(s[i]=='B') a[i]=3;
    }
    for(i=0;i<=3;i++)
        for(j=0;j<=3;j++)
            for(k=0;k<=3;k++)
            {
                set <int> s;
                if(i>0) s.insert(i);
                if(j>0) s.insert(j);
                if(k>0) s.insert(k);
                c[i][j][k]=s.size();
            }
    memset(f,-1,sizeof(f));
    cout<<cal(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