oj.uz

Submission #316754

# Submission time Handle Problem Language Result Execution time Memory
316754 2020-10-27T20:52:21 Z ant101 Popeala (CEOI16_popeala) C++14
100 / 100
 321 ms 9704 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 of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         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 10 ms 4480 KB Output is correct
3 Correct 11 ms 4480 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4736 KB Output is correct
2 Correct 61 ms 5180 KB Output is correct
3 Correct 67 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 10 ms 4480 KB Output is correct
5 Correct 11 ms 4480 KB Output is correct
6 Correct 44 ms 4736 KB Output is correct
7 Correct 61 ms 5180 KB Output is correct
8 Correct 67 ms 5376 KB Output is correct
9 Correct 86 ms 6016 KB Output is correct
10 Correct 143 ms 6528 KB Output is correct
11 Correct 235 ms 9592 KB Output is correct
12 Correct 252 ms 9600 KB Output is correct
13 Correct 316 ms 9592 KB Output is correct
14 Correct 313 ms 9704 KB Output is correct
15 Correct 321 ms 9592 KB Output is correct