Submission #261136

#	Time	Username	Problem	Language	Result	Execution time	Memory
261136		stoyan_malinin	Miners (IOI07_miners)	C++14	100 / 100	854 ms	1024 KiB

miners

#include<iostream>
#include<vector>
#include<map>
#include<set>

using namespace std;

const int MAXN = 1e5 + 5;

int n;
int a[MAXN];

int configVal[45];
int transition[45][3];

vector <vector <int>> configs;
map <vector <int>, int> configCode;

void genConfigs(vector <int> v)
{
    if(v.size()>3) return;

    configCode[v] = configs.size();
    configs.push_back(v);

    for(int i = 0;i<3;i++)
    {
        v.push_back(i);
        genConfigs(v);
        v.pop_back();
    }
}

void read()
{
    cin >> n;

    string input;
    cin >> input;

    for(int i = 0;i<n;i++)
    {
        if(input[i]=='M') a[i+1] = 0;
        else if(input[i]=='B') a[i+1] = 1;
        else if(input[i]=='F') a[i+1] = 2;
    }
}

int extendConfig(int cInd, int ext)
{
    vector <int> v = configs[cInd];

    v.push_back(ext);
    if(v.size()>3) v.erase(v.begin());

    return configCode[v];
}

void init()
{
    genConfigs(vector <int>{});
    for(int i = 0;i<configs.size();i++)
    {
        for(int ext = 0;ext<3;ext++)
        {
            transition[i][ext] = extendConfig(i, ext);
        }
    }

    for(int i = 0;i<configs.size();i++)
    {
        set <int> s;
        for(int f: configs[i]) s.insert(f);

        configVal[i] = s.size();
    }
}

int dp[2][45][45];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    init();

    for(int i = 0;i<configs.size();i++)
    {
        for(int j = 0;j<configs.size();j++)
        {
            dp[0][i][j] = -5*MAXN;
        }
    }

    dp[0][0][0] = 0;
    for(int i = 1;i<=n;i++)
    {
        for(int c1 = 0;c1<configs.size();c1++)
            for(int c2 = 0;c2<configs.size();c2++)
                dp[i&1][c1][c2] = -5*MAXN;

        for(int c1 = 0;c1<configs.size();c1++)
        {
            for(int c2 = 0;c2<configs.size();c2++)
            {
                dp[i&1][ transition[c1][ a[i] ] ][c2] = max(dp[i&1][ transition[c1][ a[i] ] ][c2],
                                                        dp[(i&1)^1][c1][c2] + configVal[ transition[c1][ a[i] ] ]);

                dp[i&1][c1][ transition[c2][ a[i] ] ] = max(dp[i&1][c1][ transition[c2][ a[i] ] ],
                                                        dp[(i&1)^1][c1][c2] + configVal[ transition[c2][ a[i] ] ]);
            }
        }
    }

    int answer = 0;
    for(int c1 = 0;c1<configs.size();c1++)
    {
        for(int c2 = 0;c2<configs.size();c2++)
        {
            answer = max(answer, dp[n&1][c1][c2]);
        }
    }

    cout << answer << '\n';
}

Compilation message (stderr)

miners.cpp: In function 'void init()':
miners.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<configs.size();i++)
                   ~^~~~~~~~~~~~~~~
miners.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<configs.size();i++)
                   ~^~~~~~~~~~~~~~~
miners.cpp: In function 'int main()':
miners.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<configs.size();i++)
                   ~^~~~~~~~~~~~~~~
miners.cpp:91:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j<configs.size();j++)
                       ~^~~~~~~~~~~~~~~
miners.cpp:100:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int c1 = 0;c1<configs.size();c1++)
                        ~~^~~~~~~~~~~~~~~
miners.cpp:101:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int c2 = 0;c2<configs.size();c2++)
                            ~~^~~~~~~~~~~~~~~
miners.cpp:104:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int c1 = 0;c1<configs.size();c1++)
                        ~~^~~~~~~~~~~~~~~
miners.cpp:106:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int c2 = 0;c2<configs.size();c2++)
                            ~~^~~~~~~~~~~~~~~
miners.cpp:118:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int c1 = 0;c1<configs.size();c1++)
                    ~~^~~~~~~~~~~~~~~
miners.cpp:120:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int c2 = 0;c2<configs.size();c2++)
                        ~~^~~~~~~~~~~~~~~

• 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