oj.uz

Submission #30713

# Submission time Handle Problem Language Result Execution time Memory
30713 2017-07-26T08:10:56 Z jenkhai Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 11852 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 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 i=1;i<=T;i++) {
        for(int k=0;k<=S;k++) {
            dp[i][k] = INF;
        }
    } 
    
    for(int k=1;k<=S;k++) {
        for(int i=1;i<=T;i++) {
            for(int j=k-1;j<i;j++) {    
                //printf("i=%d, k=%d, j=%d\n", i, j, k);
                dp[i][k] = min(dp[i][k], dp[j][k-1] + score(j+1, i));
            }
        }
    }

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11720 KB Output is correct
2 Correct 0 ms 11720 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 11720 KB Output is correct
2 Correct 433 ms 11720 KB Output is correct
3 Correct 499 ms 11720 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 11852 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11720 KB Output is correct
2 Correct 0 ms 11720 KB Output is correct
3 Correct 439 ms 11720 KB Output is correct
4 Correct 433 ms 11720 KB Output is correct
5 Correct 499 ms 11720 KB Output is correct
6 Execution timed out 2000 ms 11852 KB Execution timed out
7 Halted 0 ms 0 KB -