oj.uz

Submission #341722

# Submission time Handle Problem Language Result Execution time Memory
341722 2020-12-30T16:04:07 Z phathnv Popeala (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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