oj.uz

답안 #341722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341722 2020-12-30T16:04:07 Z phathnv 조교 (CEOI16_popeala) C++11
100 / 100
 291 ms 10732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int T = 20001;
const int N = 51;
const int S = 51;
const int INF = 2e9 + 10;

int n, t, s, p[T], dp[S][T], last[T][N], minVal[N];
string a[N];

void ReadInput(){
    cin >> n >> t >> s;
    for(int i = 1; i <= t; i++)
        cin >> p[i];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = '*' + a[i];
    }
}

void Solve(){
    for(int i = 1; i <= t; i++)
        p[i] += p[i - 1];
    for(int i = 1; i <= t; i++)
        for(int j = 1; j <= n; j++)
            last[i][j] = (a[j][i] == '0'? i : last[i - 1][j]);

    for(int i = 1; i <= t; i++){
        last[i][0] = i;
        sort(last[i], last[i] + 1 + n);
    }

    for(int i = 0; i <= s; i++)
        for(int j = 0; j <= t; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for(int i = 1; i <= s; i++){
        for(int j = 0; j <= n; j++)
            minVal[j] = INF;
        for(int j = 1; j <= t; j++)
            for(int k = 0; k <= n; k++){
                for(int l = last[j - 1][k]; l < last[j][k]; l++)
                    minVal[k] = min(minVal[k], dp[i - 1][l] - p[l] * k);
                dp[i][j] = min(dp[i][j], minVal[k] + p[j] * k);
            }
    }

    for(int i = 1; i <= s; i++)
        cout << dp[i][t] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ReadInput();
    Solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 748 KB Output is correct
2 Correct 7 ms 748 KB Output is correct
3 Correct 8 ms 748 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1516 KB Output is correct
2 Correct 59 ms 1900 KB Output is correct
3 Correct 59 ms 2540 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 9 ms 748 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 8 ms 748 KB Output is correct
6 Correct 40 ms 1516 KB Output is correct
7 Correct 59 ms 1900 KB Output is correct
8 Correct 59 ms 2540 KB Output is correct
9 Correct 73 ms 3936 KB Output is correct
10 Correct 131 ms 4864 KB Output is correct
11 Correct 200 ms 10476 KB Output is correct
12 Correct 215 ms 10604 KB Output is correct
13 Correct 291 ms 10624 KB Output is correct
14 Correct 286 ms 10604 KB Output is correct
15 Correct 288 ms 10732 KB Output is correct