Submission #350786

#	Time	Username	Problem	Language	Result	Execution time	Memory
350786		doowey	Popeala (CEOI16_popeala)	C++14	100 / 100	1954 ms	21672 KiB

popeala

#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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74