oj.uz

답안 #316754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316754 2020-10-27T20:52:21 Z ant101 조교 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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