Submission #537043

#	Time	Username	Problem	Language	Result	Execution time	Memory
537043		dantoh000	Popeala (CEOI16_popeala)	C++14	0 / 100	98 ms	2456 KiB

popeala

#include <bits/stdc++.h>
using namespace std;
int n,t,s;
int p[4005];
int r[55][4005];
int dp[4005][55];
int ct[55][4005];
const int INF = 2000000001;
int opt[4005][55];
int cost(int l, int r){
    int ret = 0;
    for (int i = 0; i < n; i++){
        if (ct[i][r] - ct[i][l-1] == 0){
            ret++;
        }
    }
    ret *= (p[r] - p[l-1]);
    return ret;
}
void dnc(int s, int e, int l, int r, int k){

    int m = (s+e)/2;
    dp[m][k] = INF;
    //printf("k=%d: %d %d %d %d\n",k,s,e,l,r);
    for (int i = max(l,k-1); i <= min(r,m-1); i++){
        int nc = dp[i][k-1] + cost(i+1,m);
        //printf("group %d %d = %d\n",i+1,m,nc);
        if (dp[m][k] > nc){
            dp[m][k] = nc;
            opt[m][k] = i;
        }
    }
    //printf("opt %d %d = %d\n",m,k,opt[m][k]);
    //printf("dp %d %d = %d\n",m,k,dp[m][k]);
    if (s<m) dnc(s,m,l,opt[m][k],k);
    if (m<e) dnc(m+1,e,opt[m][k],r,k);
}

int main(){
    scanf("%d%d%d",&n,&t,&s);
    for (int i = 1; i <= t; i++){
        scanf("%d",&p[i]);
        p[i] += p[i-1];
    }

    for (int i = 0; i < n; i++){
        for (int j = 1 ; j <= t; j++){
            char ch;
            scanf(" %c",&ch);
            r[i][j] = ch-'0';
            if (r[i][j] == 0) ct[i][j] = 1;
            ct[i][j] += ct[i][j-1];
        }
    }

    for (int i = 1; i <= t; i++){
        dp[i][1] = cost(1,i);
        //printf("%d ",dp[i][1]);
    }
    printf("%d\n",dp[t][1]);
    for (int i = 2; i <= s; i++){
        dnc(1,t,1,t,i);
        printf("%d\n",dp[t][i]);
    }

}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d%d%d",&n,&t,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d",&p[i]);
      |         ~~~~~^~~~~~~~~~~~
popeala.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |             scanf(" %c",&ch);
      |             ~~~~~^~~~~~~~~~~

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