oj.uz

답안 #255719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255719 2020-08-01T16:59:00 Z dolphingarlic 조교 (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

# 결과 실행 시간 메모리 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 9 ms 4480 KB Output is correct
3 Correct 10 ms 4480 KB Output is correct

Subtask #3
9.0 / 9.0

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

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