oj.uz

Submission #683027

# Submission time Handle Problem Language Result Execution time Memory
683027 2023-01-17T14:46:36 Z bin9638 Popeala (CEOI16_popeala) C++17
0 / 100
 36 ms 11092 KB 
#include<bits/stdc++.h>

using namespace std;
#define N  20010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

int n,S,T,a[N],pre[55][N],ktr[55][N],bit[N],dp[N][55];

void update(int u,int val)
{
    for(;u<=T;u+=u&(-u))
        bit[u]+=val;
}

int get(int u)
{
    int res=0;
    for(;u>0;u-=u&(-u))
        res+=bit[u];
    return res;
}

int32_t main()
{
    //freopen("A.inp","r",stdin);
  //  freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>T>>S;
    for(int i=1;i<=T;i++)
    {
        cin>>a[i];
        a[i]=a[i-1]+a[i];
        //cout<<a[i]<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        string st;
        cin>>st;
        st=" "+st;
        for(int j=1;j<=T;j++)
            ktr[i][j]=(st[j]=='1');
        //for(int j=1;j<=T;j++)cout<<i<<" "<<j<<" "<<ktr[i][j]<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=T;j++)
            if(ktr[i][j]==0)
                pre[i][j]=j;
                    else pre[i][j]=pre[i][j-1];
        //for(int j=1;j<=T;j++)cout<<i<<" "<<j<<" "<<pre[i][j]<<endl;
    }
    memset(dp,0x3f3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=T;i++)
    {
        for(int j=1;j<=n;j++)
            update(pre[j][i]+1,1);
        for(int j=1;j<=S;j++)
        {
            int l=j,r=i;
            while(r-l>=4)
            {
                int k=(l+r)/2;
                if(dp[k-1][j-1]+get(k)*(a[i]-a[k-1])<=dp[k][j-1]+get(k+1)*(a[i]-a[k]))
                {
                    r=k;
                }else
                {
                    l=k+1;
                }
            }
            for(int k=l;k<=r;k++)
            {
               // if(i==T)cout<<k<<" "<<get(k)<<" "<<(a[i]-a[k-1])<<endl;
                dp[i][j]=min(dp[i][j],dp[k-1][j-1]+get(k)*(a[i]-a[k-1]));
            }
        }
        for(int j=1;j<=n;j++)
            update(pre[j][i]+1,-1);
    }
    for(int i=1;i<=S;i++)
        cout<<dp[T][i]<<"\n";
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Incorrect 4 ms 9172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Incorrect 4 ms 9172 KB Output isn't correct
3 Halted 0 ms 0 KB -