oj.uz

Submission #536658

# Submission time Handle Problem Language Result Execution time Memory
536658 2022-03-13T17:25:19 Z timreizin Miners (IOI07_miners) C++17
100 / 100
 899 ms 664 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <array>
#include <set>

using namespace std;

using ll = long long;

array<int, 4> itod(int j)
{
    array<int, 4> dim;
    for (int i = 0; i < 4; ++i)
    {
        dim[i] = j % 4;
        j /= 4;
    }
    return dim;;
}

int dtoi(array<int, 4> &dim)
{
    int j = 0;
    for (int i = 3; i >= 0; --i) j = j * 4 + dim[i];
    return j;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;
    array<int, 256> dp, ndp;
    for (int i = 0; i < 256; ++i) dp[i] = -1e9;
    dp[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = (s[i] == 'M' ? 1 : (s[i] == 'F' ? 2 : 3));
        for (int j = 0; j < 256; ++j) ndp[j] = -1e9;
        for (int j = 0; j < 256; ++j)
        {
            if (dp[j] == -1e9) continue;
            array<int, 4> dim = itod(j);
            if ((dim[1] == 0 && dim[0] != 0) || (dim[3] == 0 && dim[2] != 0)) continue;
            set<int> help{dim[0], dim[1], l};
            help.erase(0);
            array<int, 4> ndim = dim;
            ndim[0] = ndim[1];
            ndim[1] = l;
            int ind = dtoi(ndim);
            ndp[ind] = max(ndp[ind], dp[j] + (int)help.size());
            ndim = dim;
            help = set<int>{dim[2], dim[3], l};
            help.erase(0);
            ndim[2] = ndim[3];
            ndim[3] = l;
            ind = dtoi(ndim);
            ndp[ind] = max(ndp[ind], dp[j] + (int)help.size());
        }
        swap(dp, ndp);
    }
    cout << *max_element(dp.begin(), dp.end());
    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 224 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 212 KB Output is correct

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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