oj.uz

Submission #683028

# Submission time Handle Problem Language Result Execution time Memory
683028 2023-01-17T14:47:09 Z bin9638 Popeala (CEOI16_popeala) C++17
17 / 100
 2000 ms 13132 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;
         
            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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8916 KB Output is correct
2 Correct 4 ms 9172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9760 KB Output is correct
2 Correct 29 ms 9676 KB Output is correct
3 Correct 29 ms 9684 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 11084 KB Output is correct
2 Correct 1194 ms 11920 KB Output is correct
3 Execution timed out 2071 ms 13132 KB Time limit exceeded
4 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 Correct 4 ms 9172 KB Output is correct
3 Correct 29 ms 9760 KB Output is correct
4 Correct 29 ms 9676 KB Output is correct
5 Correct 29 ms 9684 KB Output is correct
6 Correct 616 ms 11084 KB Output is correct
7 Correct 1194 ms 11920 KB Output is correct
8 Execution timed out 2071 ms 13132 KB Time limit exceeded
9 Halted 0 ms 0 KB -