Submission #531762

#	Time	Username	Problem	Language	Result	Execution time	Memory
531762		KoD	Popeala (CEOI16_popeala)	C++17	100 / 100	406 ms	6548 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74