Submission #165373

#	Time	Username	Problem	Language	Result	Execution time	Memory
165373		Ruxandra985	Popeala (CEOI16_popeala)	C++14	0 / 100	543 ms	1784 KiB

popeala

#include <cstdio>
#include <iostream>
#define INF 3000000000
using namespace std;
long long dp[20001][51];
long long ok[20010];
long long val[20010];
char res[51][20010];
long long mask[20010];
int biti1 (long long x){
    int sol = 0;
    while (x){
        sol = sol + (x&1);
        x/=2;
    }
    return sol;
}
void solve (int j , int st , int dr , int l , int r){
    int mid = (st + dr)/2 , poz , i;
    long long nr = 0 , mini;
    //if (j == 3)
      //  printf ("a");
    if (st > dr)
        return;
    if (mid < j){
        solve(j,mid+1,dr,l,r);
        return;
    }
    mini = INF;
    poz = 0;
    /// solutia pt mid e clar in l .. r
    nr = mask[mid];
    for ( i = mid ; i >= l && i >= j ; i-- ){
        /// calculezi dp[mid][j] in fct de dp[i][j]
        nr = (nr & mask[i]);
        if (mini > dp[i-1][j-1] + (long long)biti1(nr) * (val[mid] - val[i-1])){
            mini = dp[i-1][j-1] + (long long)biti1(nr) * (val[mid] - val[i-1]);
            poz = i;
        }
    }
    dp[mid][j] = mini;
    solve(j,st,mid-1,l,poz);
    solve(j,mid+1,dr,poz,r);
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,t,s,i,j,k,p;
  	long long nr;
    fscanf (fin,"%d%d%d",&n,&t,&s);
    for (i=1;i<=t;i++){
        fscanf (fin,"%lld",&val[i]);
        val[i]+=val[i-1];
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=t;j++){
            res[i][j] = fgetc(fin);
            while (res[i][j]!='1' && res[i][j]!='0')
                res[i][j] = fgetc(fin);
        }
    }
    for (j=1;j<=t;j++){
        for (i=1;i<=n;i++)
            mask[j] = mask[j] * 2 + (res[i][j] - '0');
    }
    for (i=0;i<=t;i++)
        for (j=0;j<=s;j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for (j=1;j<=s;j++){
        solve (j , 1 , t, 1, t);
        fprintf (fout,"%lld\n",dp[t][j]);
    }

    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:49:19: warning: unused variable 'k' [-Wunused-variable]
     int n,t,s,i,j,k,p;
                   ^
popeala.cpp:49:21: warning: unused variable 'p' [-Wunused-variable]
     int n,t,s,i,j,k,p;
                     ^
popeala.cpp:50:14: warning: unused variable 'nr' [-Wunused-variable]
    long long nr;
              ^~
popeala.cpp:51:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&t,&s);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:53:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%lld",&val[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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