oj.uz

Submission #157595

# Submission time Handle Problem Language Result Execution time Memory
157595 2019-10-12T13:57:25 Z stefdasca Miners (IOI07_miners) C++14
100 / 100
 1103 ms 644 KB 
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int dp[2][4][4][27][27];
bool viz[2][4][4][27][27];
int can[4][27], md[27];
int p3[] = {1, 3, 9};
int counter[4][27];
int nr(char c)
{
    if(c == 'B')
        return 0;
    if(c == 'M')
        return 1;
    return 2;
}
int proc(int hm, int nr)
{
    vector<int>c;
    for(int i = hm-1; i >= 0; --i)
    {
        c.push_back(nr / p3[i]);
        nr %= p3[i];
    }
    int ans = 1;
    sort(c.begin(), c.end());
    for(int i = 1; i < c.size(); ++i)
        ans = ans + (c[i] > c[i-1]);
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> s;
    s = ' ' + s;

    for(int i = 0; i <= 26; ++i)
        md[i] = i%9;
    can[0][0] = can[1][0] = can[2][0] = can[3][0] = 1;
    for(int i = 1; i <= 2; ++i)
        can[1][i] = can[2][i] = can[3][i] = 1;
    for(int i = 3; i <= 8; ++i)
        can[2][i] = can[3][i] = 1;
    for(int i = 9; i <= 26; ++i)
        can[3][i] = 1;

    for(int i = 0; i <= 26; ++i)
        for(int j = 1; j <= 3; ++j)
            if(can[j][i])
                counter[j][i] = proc(j, i);

    viz[0][0][0][0][0] = 1;

    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        s[i] = nr(s[i]);
        int prv = (i-1) % 2;
        int cur = i % 2;
        for(int cf = 0; cf <= 3; ++cf)
            for(int prev = 0; prev <= 26; ++prev)
            {
                if(!can[cf][prev])
                    continue;
                for(int cf2 = 0; cf2 <= 3; ++cf2)
                    for(int prev2 = 0; prev2 <= 26; ++prev2)
                    {
                        if(!can[cf2][prev])
                            continue;
                        if(!viz[prv][cf][cf2][prev][prev2])
                            continue;
                        if(dp[prv][cf][cf2][prev][prev2] + 10 <= ans)
                            continue;

                        int new_state = md[prev] * 3 + s[i];
                        int new_cf = cf+1;
                        if(new_cf == 4)
                            new_cf = 3;
                        viz[cur][new_cf][cf2][new_state][prev2] = 1;
                        dp[cur][new_cf][cf2][new_state][prev2] = max(dp[cur][new_cf][cf2][new_state][prev2], dp[prv][cf][cf2][prev][prev2] + counter[new_cf][new_state]);
                        ans = max(ans, dp[cur][new_cf][cf2][new_state][prev2]);


                        new_state = md[prev2] * 3 + s[i];
                        new_cf = cf2 + 1;
                        if(new_cf == 4)
                            new_cf = 3;
                        viz[cur][cf][new_cf][prev][new_state] = 1;
                        dp[cur][cf][new_cf][prev][new_state] = max(dp[cur][cf][new_cf][prev][new_state], dp[prv][cf][cf2][prev][prev2] + counter[new_cf][new_state]);

                        ans = max(ans, dp[cur][cf][new_cf][prev][new_state]);
                    }
            }
    }
    cout << ans;
    return 0;
}

Compilation message

miners.cpp: In function 'int proc(int, int)':
miners.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < c.size(); ++i)
                    ~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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