oj.uz

Submission #261136

# Submission time Handle Problem Language Result Execution time Memory
261136 2020-08-11T12:27:28 Z stoyan_malinin Miners (IOI07_miners) C++14
100 / 100
 854 ms 1024 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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