oj.uz

Submission #538609

# Submission time Handle Problem Language Result Execution time Memory
538609 2022-03-17T08:24:38 Z alextodoran Popeala (CEOI16_popeala) C++17
100 / 100
 1605 ms 70764 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int T_MAX = 20000;
const int N_MAX = 50;
const int S_MAX = 50;
const int BITS = 15;

int T, N, S;
int points[T_MAX + 2];
bool solved[N_MAX + 2][T_MAX + 2];

int pref[T_MAX + 2];
int streak[T_MAX + 2][N_MAX + 2];

int minSum[S_MAX + 2][T_MAX + 2];

int lg2[T_MAX + 2];
int rmin[N_MAX + 2][T_MAX + 2][BITS];
void build (int k, int arr[]) {
    for (int t = 0; t <= T; t++) {
        rmin[k][t][0] = arr[t];
    }
    for (int b = 1; b < BITS; b++) {
        for (int t = 0; t + (1 << b) - 1 <= T; t++) {
            rmin[k][t][b] = min(rmin[k][t][b - 1], rmin[k][t + (1 << (b - 1))][b - 1]);
        }
    }
}
int query (int k, int l, int r) {
    int b = lg2[r - l + 1];
    return min(rmin[k][l][b], rmin[k][r - (1 << b) + 1][b]);
}

int arr[T_MAX + 2];

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> T >> S;
    for (int t = 1; t <= T; t++) {
        cin >> points[t];
        pref[t] = pref[t - 1] + points[t];
    }
    for (int i = 1; i <= N; i++) {
        string str;
        cin >> str;
        for (int t = 1; t <= T; t++) {
            solved[i][t] = (str[t - 1] == '1');
        }
    }
    for (int t = 1; t <= T; t++) {
        for (int i = 1; i <= N; i++) {
            streak[t][i] = (solved[i][t] == true ? streak[t - 1][i] + 1 : 0);
        }
    }
    for (int t = 1; t <= T; t++) {
        for (int i = 1; i <= N; i++) {
            streak[t][i] = t - streak[t][i] + 1;
        }
        streak[t][0] = 1;
        streak[t][N + 1] = T + 1;
        sort(streak[t] + 0, streak[t] + N + 1);
    }

    for (int x = 1; x <= T; x++) {
        lg2[x] = lg2[x - 1];
        if ((1 << (lg2[x] + 1)) <= x) {
            lg2[x]++;
        }
    }

    for (int t = 1; t <= T; t++) {
        minSum[0][t] = INT_MAX;
    }
    for (int s = 1; s <= S; s++) {
        for (int k = 0; k <= N; k++) {
            for (int t = 0; t <= T; t++) {
                if (minSum[s - 1][t] < INT_MAX) {
                    arr[t] = minSum[s - 1][t] - pref[t] * k;
                } else {
                    arr[t] = INT_MAX;
                }
            }
            build(k, arr);
        }
        minSum[s][0] = INT_MAX;
        for (int t = 1; t <= T; t++) {
            minSum[s][t] = INT_MAX;
            for (int k = 0; k <= N; k++) {
                int l = streak[t][k], r = min(streak[t][k + 1] - 1, t);
                if (l <= r) {
                    int sum = query(k, l - 1, r - 1);
                    if (sum < INT_MAX) {
                        minSum[s][t] = min(minSum[s][t], sum + pref[t] * k);
                    }
                }
            }
        }
        cout << minSum[s][T] << "\n";
    }

    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2900 KB Output is correct
2 Correct 21 ms 2772 KB Output is correct
3 Correct 25 ms 2948 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8532 KB Output is correct
2 Correct 222 ms 11472 KB Output is correct
3 Correct 288 ms 15088 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 20 ms 2900 KB Output is correct
4 Correct 21 ms 2772 KB Output is correct
5 Correct 25 ms 2948 KB Output is correct
6 Correct 127 ms 8532 KB Output is correct
7 Correct 222 ms 11472 KB Output is correct
8 Correct 288 ms 15088 KB Output is correct
9 Correct 442 ms 23628 KB Output is correct
10 Correct 694 ms 30572 KB Output is correct
11 Correct 1520 ms 67324 KB Output is correct
12 Correct 1579 ms 70704 KB Output is correct
13 Correct 1605 ms 70676 KB Output is correct
14 Correct 1594 ms 70764 KB Output is correct
15 Correct 1573 ms 70632 KB Output is correct