oj.uz

Submission #30661

# Submission time Handle Problem Language Result Execution time Memory
30661 2017-07-26T03:07:51 Z jenkhai Popeala (CEOI16_popeala) C++14
0 / 100
 139 ms 11848 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11716 KB Output is correct
2 Incorrect 0 ms 11716 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 11848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11716 KB Output is correct
2 Incorrect 0 ms 11716 KB Output isn't correct