oj.uz

Submission #785896

# Submission time Handle Problem Language Result Execution time Memory
785896 2023-07-17T18:06:50 Z Andrei Popeala (CEOI16_popeala) C++17
100 / 100
 503 ms 15112 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()
{
    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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1100 KB Output is correct
2 Correct 11 ms 984 KB Output is correct
3 Correct 10 ms 1120 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2316 KB Output is correct
2 Correct 63 ms 2928 KB Output is correct
3 Correct 86 ms 3696 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 10 ms 1100 KB Output is correct
4 Correct 11 ms 984 KB Output is correct
5 Correct 10 ms 1120 KB Output is correct
6 Correct 43 ms 2316 KB Output is correct
7 Correct 63 ms 2928 KB Output is correct
8 Correct 86 ms 3696 KB Output is correct
9 Correct 157 ms 5540 KB Output is correct
10 Correct 198 ms 7008 KB Output is correct
11 Correct 463 ms 14880 KB Output is correct
12 Correct 503 ms 15112 KB Output is correct
13 Correct 487 ms 15052 KB Output is correct
14 Correct 486 ms 15040 KB Output is correct
15 Correct 493 ms 15084 KB Output is correct