oj.uz

Submission #785895

# Submission time Handle Problem Language Result Execution time Memory
785895 2023-07-17T18:05:45 Z Andrei Popeala (CEOI16_popeala) C++17
0 / 100
 1 ms 212 KB 
#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()
{
    fin>>n>>t>>s;
    for(int i=1; i<=t; i++)
        fin>>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;
            fin>>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++)
        fout<<dp[t][k]<<"\n";

    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

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