oj.uz

Submission #351168

# Submission time Handle Problem Language Result Execution time Memory
351168 2021-01-19T13:28:20 Z apostoldaniel854 Miners (IOI07_miners) C++14
68 / 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 0;
    if (ch == 'F')
        return 1;
    return 2;
}
inline int get_dist (vector <int> &v) {
    vector <int> f (3);
    for (int x : v)
        f[x] = 1;
    return f[0] + f[1] + f[2];
}

vector <int> add (vector <int> v, int x) {
    if (v.size () < 3) {
        v.pb (x);
        return v;
    }
    else {
        return {v[1], v[2], x};
    }
}
void upd (int &a, int b) {
    if (a < b)
        a = b;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (); cout.tie (0);

    map <pair <vector <int>, vector <int>>, int> dp;
    int n;
    cin >> n;
    string shipments_order;
    cin >> shipments_order;
    dp[{{}, {}}] = 0;
    for (char shipment : shipments_order) {
        int x = code (shipment);
        map <pair <vector <int>, vector <int>>, int> new_dp;
        for (auto prev_state : dp) {
            int value = prev_state.second;
            vector <int> first_mine = prev_state.first.first;
            vector <int> second_mine = prev_state.first.second;
            vector <int> new_first_mine = add (first_mine, x);
            vector <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));
        }
        dp = new_dp;
    }
    int ans = 0;
    for (auto state : dp)
        ans = max (ans, state.second);
    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 2 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 2 ms 364 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 150 ms 384 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1578 ms 364 KB Time limit exceeded

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 492 KB Time limit exceeded

Subtask #11
0 / 8.0

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

Subtask #12
0 / 8.0

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