oj.uz

Submission #155876

# Submission time Handle Problem Language Result Execution time Memory
155876 2019-10-01T14:18:17 Z Ruxandra985 Popeala (CEOI16_popeala) C++14
0 / 100
 87 ms 16248 KB 
/// cred ca nu e bn upsi
#include <cstdio>

using namespace std;
struct dinamic{
    int val , poz;
} dp[51][20001];
bool f[51][51][20001];
char ok[20010][51];
int val[20010];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n,t,s,i,j,k,pant,cnt;
    fscanf (fin,"%d%d%d",&n,&t,&s);
    for (i=1;i<=t;i++){
        fscanf (fin,"%d",&val[i]);
        val[i]+=val[i-1];
    }
    for (i=1;i<=n;i++){
        fgetc(fin);
        for (j=1;j<=t;j++)
            ok[i][j]=fgetc(fin)-'0';
    }
    for (i=1;i<=n;i++)
        f[i][1][0] = 1;
    for (i=1;i<=t;i++){
        cnt = 0;
        for (k=1;k<=n;k++){
            f[k][1][i] = (f[k][1][i-1] & ok[k][i]);
            if (f[k][1][i])
                cnt++;
        }
        dp[1][i].poz = 1;
        dp[1][i].val = cnt * val[i];
    }
    for (i=2;i<=t;i++){
        for (j=2;j<=s && j<=i;j++){
            dp[j][i].val = 2000000000;
            if (j <= i-1){
                pant = dp[j][i-1].poz;
                cnt = 0;
                for (k=1;k<=n;k++){
                    f[k][j][i] = (f[k][j][i-1] & ok[k][i]);
                    if (f[k][j][i])
                        cnt++;
                }

                dp[j][i].val = cnt * (val[i] - val[pant-1]) + dp[j-1][pant-1].val;
                dp[j][i].poz = pant;
            }
            cnt = 0;
            for (k=1;k<=n;k++){
                if (ok[k][i])
                    cnt++;
            }
            if (dp[j][i].val > cnt * (val[i] - val[i-1]) + dp[j-1][i-1].val){
                dp[j][i].val = cnt * (val[i] - val[i-1]) + dp[j-1][i-1].val;
                dp[j][i].poz = i;
                for (k=1;k<=n;k++){
                    f[k][j][i] = ok[k][i];
                }
            }
        }
    }
    for (j=1;j<=s;j++)
        fprintf (fout,"%d\n",dp[j][t].val);
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:16: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:18:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&val[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 2552 KB Output isn't correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 4 ms 2552 KB Output isn't correct