oj.uz

Submission #587380

# Submission time Handle Problem Language Result Execution time Memory
587380 2022-07-01T18:10:08 Z Bench0310 Miners (IOI07_miners) C++17
100 / 100
 1153 ms 528 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int dp[40][40];
int ndp[40][40];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    string opt="XMFB";
    vector<string> st;
    map<string,int> h;
    for(int a=0;a<4;a++)
    {
        for(int b=0;b<4;b++)
        {
            for(int c=0;c<4;c++)
            {
                bool ok=1;
                bool nonx=0;
                for(int x:{c,b,a})
                {
                    nonx|=(x!=0);
                    if(x==0) ok&=(!nonx);
                }
                if(ok)
                {
                    string t=string(1,opt[a])+string(1,opt[b])+string(1,opt[c]);
                    h[t]=st.size();
                    st.push_back(t);
                }
            }
        }
    }
    const int N=40;
    vector<int> score(N,0);
    for(int i=0;i<N;i++)
    {
        set<char> tmp;
        for(char c:st[i]) if(c!='X') tmp.insert(c);
        score[i]=tmp.size();
    }
    vector<array<int,3>> mv(N,{-1,-1,-1});
    for(int i=0;i<N;i++)
    {
        for(int j=1;j<=3;j++)
        {
            string tmp=opt[j]+st[i];
            tmp.pop_back();
            mv[i][j]=h[tmp];
        }
    }
    memset(dp,0b10000000,sizeof(dp));
    dp[0][0]=0;
    auto chmax=[&](int &a,int b){a=max(a,b);};
    string s;
    cin >> s;
    for(char c:s)
    {
        memset(ndp,0b10000000,sizeof(ndp));
        int t=opt.find(c);
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                int nj=mv[j][t];
                chmax(ndp[nj][k],dp[j][k]+score[nj]);
                int nk=mv[k][t];
                chmax(ndp[j][nk],dp[j][k]+score[nk]);
            }
        }
        memcpy(dp,ndp,sizeof(ndp));
    }
    int res=0;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) chmax(res,dp[i][j]);
    cout << res << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 360 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 340 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 340 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 376 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 508 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 528 KB Output is correct