oj.uz

Submission #568909

# Submission time Handle Problem Language Result Execution time Memory
568909 2022-05-26T10:41:35 Z piOOE Popeala (CEOI16_popeala) C++17
100 / 100
 697 ms 9576 KB 
#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;
                    active[k] -= 1;
                }
                for (int k = last[p] + 1; k <= j; ++k) {
                    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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8560 KB Output is correct
2 Correct 18 ms 8548 KB Output is correct
3 Correct 20 ms 8564 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8532 KB Output is correct
2 Correct 108 ms 8692 KB Output is correct
3 Correct 132 ms 8764 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8276 KB Output is correct
2 Correct 5 ms 8404 KB Output is correct
3 Correct 24 ms 8560 KB Output is correct
4 Correct 18 ms 8548 KB Output is correct
5 Correct 20 ms 8564 KB Output is correct
6 Correct 68 ms 8532 KB Output is correct
7 Correct 108 ms 8692 KB Output is correct
8 Correct 132 ms 8764 KB Output is correct
9 Correct 220 ms 8916 KB Output is correct
10 Correct 305 ms 9044 KB Output is correct
11 Correct 638 ms 9556 KB Output is correct
12 Correct 620 ms 9576 KB Output is correct
13 Correct 646 ms 9576 KB Output is correct
14 Correct 697 ms 9576 KB Output is correct
15 Correct 689 ms 9572 KB Output is correct