oj.uz

Submission #490547

# Submission time Handle Problem Language Result Execution time Memory
490547 2021-11-27T23:31:27 Z SirCovidThe19th Popeala (CEOI16_popeala) C++17
100 / 100
 395 ms 18276 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long

const int mN = 55, mT = 20005;

int n, t, s, pts[mT], mat[mN][mT], lft[mT][mN]; ll dp[mT][mN];

int main(){
    cin >> n >> t >> s;
    FOR(tst, 1, t + 1) cin >> pts[tst], pts[tst] += pts[tst - 1];
    FOR(p, 1, n + 1) FOR(tst, 1, t + 1){
        char c; cin >> c;
        mat[p][tst] = c - '0';
        lft[tst][p] = (!mat[p][tst] ? tst : lft[tst - 1][p]);
    }
    FOR(tst, 1, t + 1) lft[tst][0] = tst, sort(lft[tst], lft[tst] + n + 1);

    memset(dp, 0x3f, sizeof(dp)); dp[0][0] = 0;
    FOR(subT, 1, s + 1){
        ll bst[n + 1]; memset(bst, 0x3f, sizeof(bst));
        FOR(tst, 1, t + 1){
            FOR(correct, 0, n + 1){
                FOR(x, lft[tst - 1][correct], lft[tst][correct]){
                    bst[correct] = min(bst[correct], dp[x][subT - 1] - pts[x] * correct);
                }
                dp[tst][subT] = min(dp[tst][subT], bst[correct] + pts[tst] * correct);
            }
        }
        cout<<dp[t][subT]<<"\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 9004 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 9272 KB Output is correct
2 Correct 12 ms 9292 KB Output is correct
3 Correct 14 ms 9364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 10112 KB Output is correct
2 Correct 79 ms 10444 KB Output is correct
3 Correct 95 ms 10984 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8908 KB Output is correct
2 Correct 5 ms 9004 KB Output is correct
3 Correct 16 ms 9272 KB Output is correct
4 Correct 12 ms 9292 KB Output is correct
5 Correct 14 ms 9364 KB Output is correct
6 Correct 54 ms 10112 KB Output is correct
7 Correct 79 ms 10444 KB Output is correct
8 Correct 95 ms 10984 KB Output is correct
9 Correct 95 ms 12116 KB Output is correct
10 Correct 168 ms 13124 KB Output is correct
11 Correct 278 ms 17976 KB Output is correct
12 Correct 278 ms 18276 KB Output is correct
13 Correct 395 ms 18272 KB Output is correct
14 Correct 357 ms 18268 KB Output is correct
15 Correct 362 ms 18272 KB Output is correct