Submission #683028

#	Time	Username	Problem	Language	Result	Execution time	Memory
683028		bin9638	Popeala (CEOI16_popeala)	C++17	17 / 100	2071 ms	13132 KiB

popeala

#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;
         
            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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74