oj.uz

Submission #863258

# Submission time Handle Problem Language Result Execution time Memory
863258 2023-10-20T00:21:46 Z HuyQuang_re_Zero Miners (IOI07_miners) C++14
100 / 100
 120 ms 110680 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100696 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100688 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100696 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100696 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100696 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 100700 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 101120 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 101212 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 101720 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 103260 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 108116 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 110680 KB Output is correct