oj.uz

Submission #590872

# Submission time Handle Problem Language Result Execution time Memory
590872 2022-07-06T12:32:40 Z alextodoran Popeala (CEOI16_popeala) C++17
100 / 100
 436 ms 13736 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 arr[N_MAX + 2][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 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[k][t] = minSum[s - 1][t] - pref[t] * k;
                } else {
                    arr[k][t] = INT_MAX;
                }
            }
            for (int t = 1; t <= T; t++) {
                arr[k][t] = min(arr[k][t], arr[k][t - 1]);
            }
        }
        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 = arr[k][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 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1236 KB Output is correct
2 Correct 10 ms 1236 KB Output is correct
3 Correct 11 ms 1236 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2316 KB Output is correct
2 Correct 74 ms 3020 KB Output is correct
3 Correct 90 ms 3508 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 596 KB Output is correct
3 Correct 11 ms 1236 KB Output is correct
4 Correct 10 ms 1236 KB Output is correct
5 Correct 11 ms 1236 KB Output is correct
6 Correct 47 ms 2316 KB Output is correct
7 Correct 74 ms 3020 KB Output is correct
8 Correct 90 ms 3508 KB Output is correct
9 Correct 133 ms 5220 KB Output is correct
10 Correct 180 ms 6516 KB Output is correct
11 Correct 402 ms 13324 KB Output is correct
12 Correct 400 ms 13524 KB Output is correct
13 Correct 436 ms 13736 KB Output is correct
14 Correct 415 ms 13496 KB Output is correct
15 Correct 426 ms 13556 KB Output is correct