제출 #490547

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
490547	2021-11-27 23:31:27	SirCovidThe19th	조교 (CEOI16_popeala)	C++17	100 / 100	395 ms	18276 KiB

popeala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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);
            }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74