Submission #223558

#	Time	Username	Problem	Language	Result	Execution time	Memory
223558		MKopchev	Popeala (CEOI16_popeala)	C++14	17 / 100	2084 ms	1588 KiB

popeala

#include<bits/stdc++.h>
using namespace std;
const int nmax=50+5,tmax=20000+5,inf=2e9+42;

int n,tasks,want;

int points[tmax];

bool solved[nmax][tmax];

int nxt_bad[nmax][tmax];

int pref[nmax];

int ask(int l,int r)
{
    int ret=0,sum=pref[r]-pref[l-1];

    for(int i=1;i<=n;i++)
        if(nxt_bad[i][l]>r)ret=ret+sum;

    return ret;
}

int dp[nmax][tmax];
int main()
{
    scanf("%i%i%i",&n,&tasks,&want);

    for(int i=1;i<=tasks;i++)scanf("%i",&points[i]);

    for(int i=1;i<=tasks;i++)pref[i]=pref[i-1]+points[i];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=tasks;j++)
        {
            char in=getchar();
            while(in!='0'&&in!='1')in=getchar();

            if(in=='1')solved[i][j]=1;
        }

    for(int i=1;i<=n;i++)
    {
        nxt_bad[i][tasks+1]=tasks+1;

        for(int j=tasks;j>=1;j--)
            if(solved[i][j]==0)nxt_bad[i][j]=j;
            else nxt_bad[i][j]=nxt_bad[i][j+1];
    }
    /*
    for(int i=1;i<=n;i++)
        for(int j=1;j<=tasks;j++)
            cout<<i<<" "<<j<<" -> "<<nxt_bad[i][j]<<endl;
    */
    for(int i=1;i<=tasks;i++)
        dp[0][i]=inf;

    for(int sub=1;sub<=want;sub++)
    {
        dp[sub][0]=inf;

        for(int i=1;i<=tasks;i++)
        {
            dp[sub][i]=inf;
            for(int cur=i;cur>=1;cur--)
                if(dp[sub-1][cur-1]!=inf)
                {
                    dp[sub][i]=min(dp[sub][i],dp[sub-1][cur-1]+ask(cur,i));
                }
            //cout<<sub<<" "<<i<<" -> "<<dp[sub][i]<<endl;
        }
        printf("%i\n",dp[sub][tasks]);
    }

    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i",&n,&tasks,&want);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:30:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=tasks;i++)scanf("%i",&points[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~

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