oj.uz

Submission #255719

# Submission time Handle Problem Language Result Execution time Memory
255719 2020-08-01T16:59:00 Z dolphingarlic Popeala (CEOI16_popeala) C++14
100 / 100
 309 ms 9720 KB 
#include <bits/stdc++.h>
using namespace std;

int points[20001], prv[20001][51], best[51], dp[20001][51];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, t, s;
    cin >> n >> t >> s;
    for (int i = 1; i <= t; i++) {
        cin >> points[i];
        points[i] += points[i - 1];
    }
    for (int j = 1; j <= n; j++) {
        string solved;
        cin >> solved;
        for (int i = 0; i < solved.size(); i++) {
            if (solved[i] == '1') prv[i + 1][j] = prv[i][j];
            else prv[i + 1][j] = i + 1;
        }
    }
    for (int i = 1; i <= t; i++) {
        prv[i][0] = i;
        sort(prv[i], prv[i] + n + 1);
    }

    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (int j = 1; j <= s; j++) {
        memset(best, 0x3f, sizeof best);
        for (int i = 1; i <= t; i++) {
            for (int k = 0; k <= n; k++) {
                for (int l = prv[i - 1][k]; l < prv[i][k]; l++) {
                    best[k] = min(best[k], dp[l][j - 1] - points[l] * k);
                }
                dp[i][j] = min(dp[i][j], best[k] + points[i] * k);
            }
        }
        cout << dp[t][j] << '\n';
    }
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:18:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < solved.size(); i++) {
                         ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4992 KB Output is correct
2 Correct 61 ms 5120 KB Output is correct
3 Correct 64 ms 5376 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4352 KB Output is correct
2 Correct 3 ms 4352 KB Output is correct
3 Correct 11 ms 4480 KB Output is correct
4 Correct 9 ms 4480 KB Output is correct
5 Correct 10 ms 4480 KB Output is correct
6 Correct 46 ms 4992 KB Output is correct
7 Correct 61 ms 5120 KB Output is correct
8 Correct 64 ms 5376 KB Output is correct
9 Correct 76 ms 6016 KB Output is correct
10 Correct 141 ms 6540 KB Output is correct
11 Correct 208 ms 9668 KB Output is correct
12 Correct 222 ms 9600 KB Output is correct
13 Correct 309 ms 9720 KB Output is correct
14 Correct 303 ms 9600 KB Output is correct
15 Correct 305 ms 9720 KB Output is correct