Submission #587380

#	Time	Username	Problem	Language	Result	Execution time	Memory
587380		Bench0310	Miners (IOI07_miners)	C++17	100 / 100	1153 ms	528 KiB

miners

#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 / 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