oj.uz

Submission #531762

# Submission time Handle Problem Language Result Execution time Memory
531762 2022-03-01T12:27:56 Z KoD Popeala (CEOI16_popeala) C++17
100 / 100
 406 ms 6548 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int inf = std::numeric_limits<int>::max();

int main() {
    int N, T, S;
    std::cin >> N >> T >> S;
    vector<int> sum(T + 1);
    for (int i = 0; i < T; ++i) {
        std::cin >> sum[i + 1];
        sum[i + 1] += sum[i];   
    }
    vector fail(T + 1, vector(N + 1, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < T; ++j) {
            char c;
            std::cin >> c;
            fail[j + 1][i] = c == '0' ? j + 1 : fail[j][i];
        }
    }
    for (int i = 0; i <= T; ++i) {
        fail[i][N] = i;
        std::sort(fail[i].begin(), fail[i].end());
    }
    vector<int> dp(T + 1, inf);
    dp[0] = 0;
    for (int s = 1; s <= S; ++s) {
        vector<int> next(T + 1, inf), memo(N + 1, inf);
        for (int i = 1; i <= T; ++i) {
            for (int j = 0; j <= N; ++j) {
                for (int k = fail[i - 1][j]; k < fail[i][j]; ++k) {
                    if (dp[k] != inf) {
                        memo[j] = std::min(memo[j], dp[k] - sum[k] * j);
                    }
                }
                if (memo[j] != inf) {
                    next[i] = std::min(next[i], memo[j] + sum[i] * j);
                }
            }
        }
        dp = std::move(next);
        std::cout << dp[T] << '\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 436 KB Output is correct
2 Correct 11 ms 432 KB Output is correct
3 Correct 11 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 912 KB Output is correct
2 Correct 68 ms 1180 KB Output is correct
3 Correct 78 ms 1524 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 10 ms 436 KB Output is correct
4 Correct 11 ms 432 KB Output is correct
5 Correct 11 ms 332 KB Output is correct
6 Correct 62 ms 912 KB Output is correct
7 Correct 68 ms 1180 KB Output is correct
8 Correct 78 ms 1524 KB Output is correct
9 Correct 106 ms 2248 KB Output is correct
10 Correct 190 ms 2936 KB Output is correct
11 Correct 306 ms 6304 KB Output is correct
12 Correct 313 ms 6520 KB Output is correct
13 Correct 406 ms 6548 KB Output is correct
14 Correct 380 ms 6508 KB Output is correct
15 Correct 378 ms 6500 KB Output is correct