oj.uz

Submission #223585

# Submission time Handle Problem Language Result Execution time Memory
223585 2020-04-15T14:05:55 Z MKopchev Popeala (CEOI16_popeala) C++14
100 / 100
 1452 ms 14816 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[tmax];

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 pref_min[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++)
        {
            pref_min[0]=inf;
            for(int i=1;i<=tasks;i++)
            {
            pref_min[i]=min(pref_min[i-1],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],pref_min[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:62: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:64: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 5 ms 896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1528 KB Output is correct
2 Correct 34 ms 1528 KB Output is correct
3 Correct 37 ms 1528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 2680 KB Output is correct
2 Correct 237 ms 3328 KB Output is correct
3 Correct 269 ms 4044 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 40 ms 1528 KB Output is correct
4 Correct 34 ms 1528 KB Output is correct
5 Correct 37 ms 1528 KB Output is correct
6 Correct 167 ms 2680 KB Output is correct
7 Correct 237 ms 3328 KB Output is correct
8 Correct 269 ms 4044 KB Output is correct
9 Correct 322 ms 5900 KB Output is correct
10 Correct 529 ms 7160 KB Output is correct
11 Correct 771 ms 14288 KB Output is correct
12 Correct 859 ms 14712 KB Output is correct
13 Correct 1452 ms 14816 KB Output is correct
14 Correct 1068 ms 14712 KB Output is correct
15 Correct 1362 ms 14716 KB Output is correct