Submission #30663

#	Time	Username	Problem	Language	Result	Execution time	Memory
30663		jenkhai	Popeala (CEOI16_popeala)	C++14	17 / 100	2000 ms	11848 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 2e4+10;
const int MAXN = 50+10;
const int MAXS = 50+10;
const int INF = 2e9+10;
int N, T, S;
int val[MAXT], valp[MAXT];
int dp[MAXT][MAXS];
vector<string> res;
int pf[MAXN][MAXT];

int score(int l, int r) {
    int subtask_score = valp[r] - valp[l-1];
    int ret = 0;        
    for(int i=1;i<=N;i++) {
        if(pf[i][r] - pf[i][l-1] == (r-l+1)) ret += subtask_score;
    }
    //printf("%d %d per subtask:%d, total=%d\n", l, r, subtask_score, ret);
    return ret;
}

int solve(int i, int k) {
    if(k==0 && i>0) return INF;
    if(k>i) return INF;
    if(i==0 && k==0) return 0;
    if(dp[i][k] != -1) return dp[i][k];
    dp[i][k] = INF;
    for(int j=1;j<=i;j++) {
        dp[i][k] = min(dp[i][k], solve(j-1, k-1) + score(j, i));
    }
    return dp[i][k];

}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> T >> S;
    for(int i=1;i<=T;i++) {
        cin >> val[i];
        valp[i] = valp[i-1] + val[i];
    }
    res.assign(N+1, ""); 
    for(int i=1;i<=N;i++) {
        cin >> res[i];
        for(int j=1;j<=T;j++) {
            pf[i][j] = pf[i][j-1] + (res[i][j-1]=='1');
        } 
    }

    for(int k=1;k<=S;k++) {
        for(int i=k;i<=T;i++) {
            dp[i][k] = -1;
        }
    }

    for(int k=1;k<=S;k++) {
        printf("%d\n", solve(T, k));
    } 
    
    
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74