Submission #568905

#	Time	Username	Problem	Language	Result	Execution time	Memory
568905		piOOE	Popeala (CEOI16_popeala)	C++17	100 / 100	678 ms	10668 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll infL = 3e18;
const int T = 20001, N = 51, S = 51;

bool solved[N][T];

ll dp[S][T];

int pref[T], arr[T], active[T], best[N], last[N];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t, s;
    cin >> n >> t >> s;
    for (int i = 1; i <= t; ++i) {
        cin >> arr[i];
        pref[i] = pref[i - 1] + arr[i];
    }
    for (int i = 1; i <= n; ++i) {
        string ss;
        cin >> ss;
        for (int j = 1; j <= t; ++j) {
            solved[i][j] = (ss[j - 1] == '1');
        }
    }
    for (int i = 0; i < S; ++i)
        fill(dp[i], dp[i] + T, infL);
    dp[0][0] = 0;
    for (int i = 1; i <= s; ++i) {
        memset(best, 0, sizeof(best));
        memset(last, 0, sizeof(last));
        for (int j = 0; j <= t; ++j)
            active[j] = n;
        for (int j = 1; j <= t; ++j) {
            auto f = [&](int l) {
                return dp[i - 1][l] + (pref[j] - pref[l]) * active[l + 1];
            };
            if (f(best[n]) > f(j - 1)) {
                best[n] = j - 1;
            }
            for (int p = 1; p <= n; ++p) {
                if (solved[p][j]) continue;
                for (int k = last[p] + 1; k <= j; ++k) {
                    best[active[k]] = 0;
                }
                for (int k = last[p] + 1; k <= j; ++k) {
                    active[k] -= 1;
                    if (f(best[active[k]]) > f(k - 1)) {
                        best[active[k]] = k - 1;
                    }
                }
                last[p] = j;
            }
            if (j < i) continue;
            for (int p = 0; p <= n; ++p) {
                ll val = f(best[p]);
                if (val < dp[i][j])
                    dp[i][j] = val;
            }
        }
        cout << dp[i][t] << '\n';
    }
    return 0;

}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74