oj.uz

Submission #223581

# Submission time Handle Problem Language Result Execution time Memory
223581 2020-04-15T13:57:32 Z MKopchev Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 5384 KB 
#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 prv_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(prv_bad[i][r]<l)ret=ret+sum;

    return ret;
}

int dp[nmax][tmax];

int moments[nmax];

int tree[1<<16];

void update(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node]=val;
        return;
    }

    int av=(l+r)/2;
    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);

    tree[node]=min(tree[node*2],tree[node*2+1]);
}

int query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];

    int av=(l+r)/2,ret=inf;

    if(lq<=av)ret=min(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=min(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
    return ret;
}

int moments_mem[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++)
    {
        for(int j=1;j<=tasks;j++)
            if(solved[i][j]==0)prv_bad[i][j]=j;
            else prv_bad[i][j]=prv_bad[i][j-1];
    }

    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++)
        {
            for(int j=1;j<=n;j++)moments[j]=prv_bad[j][i];

            sort(moments+1,moments+n+1);

            moments[n+1]=i;

            for(int w=0;w<=n+1;w++)
            {
                moments_mem[w][i]=moments[w];
            }
            //cout<<sub<<" "<<i<<" -> "<<dp[sub][i]<<endl;
        }

        for(int i=0;i<=tasks;i++)dp[sub][i]=inf;

        for(int w=0;w<=n;w++)
        for(int i=1;i<=tasks;i++)
        {
            update(1,1,tasks,i,dp[sub-1][i-1]-w*pref[i-1]);

            if(sub>i)continue;

            int lhs=moments_mem[w][i]+1,rhs=moments_mem[w+1][i];

            if(lhs>rhs)continue;

            dp[sub][i]=min(dp[sub][i],query(1,1,tasks,lhs,rhs)+w*pref[i]);

            //cout<<sub<<" "<<i<<" -> "<<dp[sub][i]<<endl;
        }
        printf("%i\n",dp[sub][tasks]);
    }

    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:60: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:62: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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 1528 KB Output is correct
2 Correct 190 ms 1528 KB Output is correct
3 Correct 195 ms 1528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 2680 KB Output is correct
2 Correct 1413 ms 3424 KB Output is correct
3 Correct 1973 ms 3960 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 205 ms 1528 KB Output is correct
4 Correct 190 ms 1528 KB Output is correct
5 Correct 195 ms 1528 KB Output is correct
6 Correct 974 ms 2680 KB Output is correct
7 Correct 1413 ms 3424 KB Output is correct
8 Correct 1973 ms 3960 KB Output is correct
9 Execution timed out 2084 ms 5384 KB Time limit exceeded
10 Halted 0 ms 0 KB -