oj.uz

Submission #237399

# Submission time Handle Problem Language Result Execution time Memory
237399 2020-06-06T13:23:31 Z Sorting Popeala (CEOI16_popeala) C++14
100 / 100
 319 ms 19280 KB 
#include <bits/stdc++.h>

using namespace std;

const int mx_N = 50 + 3;
const int mx_S = 50 + 3;
const int mx_T = 2e4 + 3;

int n, t, s;
long long dp[mx_S][mx_T];
long long p[mx_T], a[mx_T][mx_N], b[mx_N];
string r[mx_N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> t >> s;

    for(int i = 0; i < t; ++i){
        cin >> p[i + 1];
        p[i + 1] += p[i];
    }

    for(int i = 0; i < n; ++i)
        cin >> r[i];

    for(int i = 0; i < t; ++i)
        for(int j = 0; j < n; ++j)
            a[i + 1][j] = (r[j][i] & 1) ? a[i][j] : i + 1;

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

    for(int i = 1; i <= t; ++i)
        dp[0][i] = INT_MAX;
    dp[0][0] = 0;
    
    for(int i = 1; i <= s; ++i){
        for(int k = 0; k <= n; ++k)
            b[k] = INT_MAX;

        for(int j = 1; j <= t; ++j){
            dp[i][j] = INT_MAX;
            for(int k = 0; k <= n; ++k){
                for(int l = a[j - 1][k]; l < a[j][k]; ++l)
                    b[k] = min(dp[i - 1][l] - p[l] * k, b[k]);
                dp[i][j] = min(b[k] + p[j] * k, dp[i][j]);
            }
            //cout << dp[i][j] << " dp[" << i << "][" << j << "]\n";  
        }
        dp[i][0] = INT_MAX;

        cout << dp[i][t] << "\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1024 KB Output is correct
2 Correct 11 ms 1024 KB Output is correct
3 Correct 12 ms 1024 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2516 KB Output is correct
2 Correct 60 ms 3320 KB Output is correct
3 Correct 65 ms 4344 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 13 ms 1024 KB Output is correct
4 Correct 11 ms 1024 KB Output is correct
5 Correct 12 ms 1024 KB Output is correct
6 Correct 46 ms 2516 KB Output is correct
7 Correct 60 ms 3320 KB Output is correct
8 Correct 65 ms 4344 KB Output is correct
9 Correct 90 ms 6776 KB Output is correct
10 Correct 138 ms 8568 KB Output is correct
11 Correct 226 ms 19056 KB Output is correct
12 Correct 230 ms 19156 KB Output is correct
13 Correct 305 ms 19280 KB Output is correct
14 Correct 302 ms 19068 KB Output is correct
15 Correct 319 ms 19196 KB Output is correct