제출 #30661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30661		jenkhai	조교 (CEOI16_popeala)	C++14	0 / 100	139 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 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] = INF;
            for(int j=1;j<=i;j++) {
                if(j-1 > k-1) continue;
                if(k-1 > j-1) continue;
                dp[i][k] = min(dp[i][k], dp[j-1][k-1] + score(j, i));
                //printf("k=%d %d %d\n", k, j, i);

            }
        }
    }

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

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