oj.uz

Submission #253784

# Submission time Handle Problem Language Result Execution time Memory
253784 2020-07-28T16:58:10 Z yanndev Miners (IOI07_miners) C++17
100 / 100
 1219 ms 100856 KB 
#include <iostream>
#include <set>
#include <map>

const int MAX_FOOD = 1e5 + 1;
const int NO_FOOD = 0;
const int INF = 1e9;

int dp[MAX_FOOD][4][4][4][4];
std::map<char, int> foodToInt {{'F', 1}, {'M', 2}, {'B', 3}};

int score(int a, int b, int c) {
    std::set<int> vals {a, b, c};
    vals.erase(0);
    return vals.size();
}

int main() {
    int n_delivery;
    int ans = 0;
    std::string deliveries;
    std::cin >> n_delivery >> deliveries;

    for (int i = 0; i <= n_delivery; i++)
        for (int lastFoodM11 = 0; lastFoodM11 < 4; lastFoodM11++)
            for (int lastFoodM12 = 0; lastFoodM12 < 4; lastFoodM12++)
                for (int lastFoodM21 = 0; lastFoodM21 < 4; lastFoodM21++)
                    for (int lastFoodM22 = 0; lastFoodM22 < 4; lastFoodM22++)
                        dp[i][lastFoodM11][lastFoodM12][lastFoodM21][lastFoodM22] = -INF;

    dp[0][NO_FOOD][NO_FOOD][NO_FOOD][NO_FOOD] = 0;

    for (int i = 0; i < n_delivery; i++) {
        int curFood = foodToInt[deliveries[i]];
        for (int lastFoodM11 = 0; lastFoodM11 < 4; lastFoodM11++)
            for (int lastFoodM12 = 0; lastFoodM12 < 4; lastFoodM12++)
                for (int lastFoodM21 = 0; lastFoodM21 < 4; lastFoodM21++)
                    for (int lastFoodM22 = 0; lastFoodM22 < 4; lastFoodM22++)
                        if (dp[i][lastFoodM11][lastFoodM12][lastFoodM21][lastFoodM22] != -INF) {

                            dp[i + 1][lastFoodM12][curFood][lastFoodM21][lastFoodM22] = std::max(
                                    dp[i + 1][lastFoodM12][curFood][lastFoodM21][lastFoodM22],
                                    dp[i][lastFoodM11][lastFoodM12][lastFoodM21][lastFoodM22] +
                                    score(lastFoodM11, lastFoodM12, curFood)
                                    );

                            dp[i + 1][lastFoodM11][lastFoodM12][lastFoodM22][curFood] = std::max(
                                    dp[i + 1][lastFoodM11][lastFoodM12][lastFoodM22][curFood],
                                    dp[i][lastFoodM11][lastFoodM12][lastFoodM21][lastFoodM22] +
                                    score(lastFoodM21, lastFoodM22, curFood)
                                    );

                            ans = std::max(ans, std::max(
                                    dp[i + 1][lastFoodM12][curFood][lastFoodM21][lastFoodM22],
                                    dp[i + 1][lastFoodM11][lastFoodM12][lastFoodM22][curFood]
                                    ));
                        }
    }
    
    std::cout << ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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