oj.uz

Submission #351171

# Submission time Handle Problem Language Result Execution time Memory
351171 2021-01-19T13:40:53 Z apostoldaniel854 Miners (IOI07_miners) C++14
52 / 100
 1500 ms 620 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

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

int dp[MAX_MASK][MAX_MASK];
int new_dp[MAX_MASK][MAX_MASK];

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

    int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (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) {
        int x = code (shipment);
        for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                new_dp[first_mine][second_mine] = -1;
        for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++) {
                int value = dp[first_mine][second_mine];
                if (value >= 0) {
                    int new_first_mine = add (first_mine, x);
                    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 (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
            for (int second_mine = 0; second_mine < MAX_MASK; second_mine++)
                dp[first_mine][second_mine] = new_dp[first_mine][second_mine];
    }
    int ans = 0;
    for (int first_mine = 0; first_mine < MAX_MASK; first_mine++)
        for (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 364 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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #7
8.0 / 8.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 364 KB Output isn't correct

Subtask #9
8.0 / 8.0

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

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 582 ms 388 KB Output isn't correct

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1307 ms 548 KB Output isn't correct

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 620 KB Time limit exceeded