oj.uz

Submission #350786

# Submission time Handle Problem Language Result Execution time Memory
350786 2021-01-19T08:24:41 Z doowey Popeala (CEOI16_popeala) C++14
100 / 100
 1954 ms 21672 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 55;
const int M = 20010;
const ll inf = (ll)1e18;
int pv[N][M];
ll dp[N][M];
ll cum[M];
ll low[N][M];

int main(){
    fastIO;
    int n, m, sp;
    cin >> n >> m >> sp;
    for(int i = 1; i <= m ; i ++) {
        cin >> cum[i];
        cum[i] += cum[i-1];
    }
    char f;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> f;
            if(f == '0'){
                pv[i][j]=j;
            }
            else{
                pv[i][j]=pv[i][j-1];
            }
        }
    }
    for(int i = 0 ; i <= sp; i ++ ){
        for(int j = 0; j <= m ; j ++ ){
            dp[i][j]=inf;
        }
    }
    dp[0][0]=0;
    int cc;
    for(int cur = 1; cur <= sp; cur ++ ){
        for(int c = 0; c <= n; c ++ ){
            for(int q = 0; q <= m; q ++ ){
                low[c][q]=inf;
            }
            for(int q = 1; q <= m ; q ++ ){
                low[c][q]=dp[cur-1][q-1]-cum[q-1]*1ll*c;
                low[c][q]=min(low[c][q],low[c][q-1]);
            }
        }
        for(int j = 1; j <= m ; j ++ ){
            vector<int> st;
            for(int t = 1; t <= n; t ++ ){
                st.push_back(pv[t][j]);
            }
            sort(st.begin(), st.end());
            dp[cur][j]=low[n][j]+cum[j]*1ll*n;
            cc = n;
            for(int x = st.size() - 1; x >= 0; x -- ){
                cc -- ;
                dp[cur][j]=min(dp[cur][j],low[cc][st[x]]+cum[j]*1ll*cc);
            }
        }
        cout << dp[cur][m] << "\n";
    }
    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 2 ms 748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1516 KB Output is correct
2 Correct 44 ms 1544 KB Output is correct
3 Correct 44 ms 1572 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 3300 KB Output is correct
2 Correct 326 ms 4204 KB Output is correct
3 Correct 448 ms 5228 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 2 ms 748 KB Output is correct
3 Correct 46 ms 1516 KB Output is correct
4 Correct 44 ms 1544 KB Output is correct
5 Correct 44 ms 1572 KB Output is correct
6 Correct 223 ms 3300 KB Output is correct
7 Correct 326 ms 4204 KB Output is correct
8 Correct 448 ms 5228 KB Output is correct
9 Correct 639 ms 7908 KB Output is correct
10 Correct 786 ms 10016 KB Output is correct
11 Correct 1357 ms 21036 KB Output is correct
12 Correct 1555 ms 21544 KB Output is correct
13 Correct 1954 ms 21612 KB Output is correct
14 Correct 1618 ms 21672 KB Output is correct
15 Correct 1924 ms 21612 KB Output is correct