oj.uz

Submission #568905

# Submission time Handle Problem Language Result Execution time Memory
568905 2022-05-26T10:38:25 Z piOOE Popeala (CEOI16_popeala) C++17
100 / 100
 678 ms 10668 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;
                }
                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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8532 KB Output is correct
2 Correct 18 ms 8472 KB Output is correct
3 Correct 21 ms 8588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 8748 KB Output is correct
2 Correct 117 ms 8864 KB Output is correct
3 Correct 139 ms 8972 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 4 ms 8392 KB Output is correct
3 Correct 20 ms 8532 KB Output is correct
4 Correct 18 ms 8472 KB Output is correct
5 Correct 21 ms 8588 KB Output is correct
6 Correct 78 ms 8748 KB Output is correct
7 Correct 117 ms 8864 KB Output is correct
8 Correct 139 ms 8972 KB Output is correct
9 Correct 214 ms 9268 KB Output is correct
10 Correct 341 ms 9428 KB Output is correct
11 Correct 611 ms 10584 KB Output is correct
12 Correct 673 ms 10652 KB Output is correct
13 Correct 678 ms 10668 KB Output is correct
14 Correct 675 ms 10580 KB Output is correct
15 Correct 666 ms 10648 KB Output is correct