Submission #785896

#	Time	Username	Problem	Language	Result	Execution time	Memory
785896		Andrei	Popeala (CEOI16_popeala)	C++17	100 / 100	503 ms	15112 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

ifstream fin("popeala.in");
ofstream fout("popeala.out");

int n,t,s;

int points[20005];

int sumpref[20005];

bool results[55][20005];

int slin[55][20005];

int aux[200005][55];

int dp[20005][55];

int minim[20005];

int activeRows(int x,int y)
{
    int ans=0;
    for(int i=1; i<=n; i++)
        ans+=(slin[i][y]-slin[i][x]==y-x);
    return ans;
}

int main()
{
    cin>>n>>t>>s;
    for(int i=1; i<=t; i++)
        cin>>points[i];

    for(int i=1; i<=t; i++)
        sumpref[i]=sumpref[i-1]+points[i];

    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=t; j++)
        {
            char ch;
            cin>>ch;
            results[i][j]=ch-'0';
        }
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=t; j++)
            slin[i][j]=slin[i][j-1]+(int)results[i][j];

    for(int active=0; active<=n; active++)
    {
        int j=0;
        for(int i=1; i<=t; i++)
        {
            while(j+1<i && activeRows(j+1,i)<=active)
                j++;
            if(activeRows(j,i)<=active)
                aux[i][active]=j;
        }
    }

    for(int i=1; i<=t; i++)
        dp[i][1]=activeRows(0,i)*sumpref[i];

    for(int k=2; k<=s; k++)
    {
        for(int i=k; i<=t; i++)
            dp[i][k]=(int)2e9;

        for(int active=0; active<=n; active++)
        {
            minim[k-2]=2e9;
            for(int i=k-1; i<=t; i++)
                minim[i]=min(minim[i-1],dp[i][k-1]-active*sumpref[i]);

            for(int i=k; i<=t; i++)
                if(aux[i][active]>=k-1)
                    dp[i][k]=min(dp[i][k],minim[aux[i][active]]+active*sumpref[i]);
        }
    }

    for(int k=1; k<=s; k++)
        cout<<dp[t][k]<<"\n";

    return 0;
}

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