oj.uz

Submission #351176

# Submission time Handle Problem Language Result Execution time Memory
351176 2021-01-19T13:56:00 Z apostoldaniel854 Miners (IOI07_miners) C++14
100 / 100
 1217 ms 748 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

inline int code (char ch) {
    if (ch == 'M')
        return 1;
    if (ch == 'F')
        return 2;
    return 3;
}
const int MAX_MASK = (1 << 6);
int f[4];
inline int get_dist (int mask) {
    f[1] = f[2] = f[3] = 0;
    while (mask) {
        f[mask & 3] = 1;
        mask /= 4;
    }
    return f[1] + f[2] + f[3];
}

inline int add (int &mask, int &x) {
    return ((mask << 2) + x) & (MAX_MASK - 1);
}
inline void upd (int &a, int b) {
    if (a < b)
        a = b;
}

int dp[1 + MAX_MASK][1 + MAX_MASK];
int new_dp[1 + MAX_MASK][1 + MAX_MASK];

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

    register int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++)
            dp[first_mine][second_mine] = -1;
    dp[0][0] = 0;
    for (char shipment : shipments_order) {
        register int x = code (shipment);

        for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                new_dp[first_mine][second_mine] = -1;

        for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) {
                register int value = dp[first_mine][second_mine];
                if (value >= 0) {
                    register int new_first_mine = add (first_mine, x);
                    register int new_second_mine = add (second_mine, x);
                    upd (new_dp[new_first_mine][second_mine], value + get_dist (new_first_mine));
                    upd (new_dp[first_mine][new_second_mine], value + get_dist (new_second_mine));
                }
            }

        for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (register  int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                dp[first_mine][second_mine] = new_dp[first_mine][second_mine];
    }

    register int ans = 0;
    for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++)
            upd (ans, dp[first_mine][second_mine]);
    cout << ans << "\n";
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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