Submission #589769

#	Time	Username	Problem	Language	Result	Execution time	Memory
589769		andrei_boaca	Popeala (CEOI16_popeala)	C++14	0 / 100	2094 ms	28496 KiB

popeala

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct date
{
    ll val,cntmin,cntmax;
} dp[20005];
ll cost[4005][4005];
int n,t,s;
int val[20005];
bool have[55][20005];
bool bad[55];
int mycost[55];
void makedp(ll c)
{
    dp[0].val=0;
    dp[0].cntmin=0;
    dp[0].cntmax=0;
    for(int i=1;i<=t;i++)
    {
        dp[i].val=1e16;
        dp[i].cntmin=2e9;
        dp[i].cntmax=2e9;
        for(int j=i-1;j>=0;j--)
        {
            ll val=dp[j].val+cost[j+1][i]-c;
            ll nrmin=dp[j].cntmin+1;
            ll nrmax=dp[j].cntmax+1;
            if(val<dp[i].val)
            {
                dp[i].val=val;
                dp[i].cntmin=nrmin;
                dp[i].cntmax=nrmax;
            }
            else if(val==dp[i].val)
                {
                    dp[i].cntmin=min(dp[i].cntmin,nrmin);
                    dp[i].cntmax=max(dp[i].cntmax,nrmax);
                }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>t>>s;
    for(int i=1;i<=t;i++)
        cin>>val[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=t;j++)
        {
            char c;
            cin>>c;
            have[i][j]=c-'0';
        }
    for(int i=1;i<=t;i++)
    {
        for(int j=1;j<=n;j++)
        {
            bad[j]=0;
            mycost[j]=0;
        }
        int cur=0;
        for(int j=i;j<=t;j++)
        {
            for(int k=1;k<=n;k++)
                if(!bad[k])
                {
                    if(have[k][j])
                    {
                        cur+=val[j];
                        mycost[k]+=val[j];
                    }
                    else
                    {
                        bad[k]=1;
                        cur-=mycost[k];
                        mycost[k]=0;
                    }
                }
            cost[i][j]=cur;
        }
    }
    for(int a=1;a<=s;a++)
    {
        ll st=1;
        ll dr=1e9;
        while(st<=dr)
        {
            ll mij=(st+dr)/2;
            makedp(mij);
            if(a>=dp[t].cntmin&&a<=dp[t].cntmax)
            {
                cout<<dp[t].val+a*mij;
                break;
            }
            if(a>dp[t].cntmax)
                st=mij+1;
            else if(a<dp[t].cntmin)
                dr=mij-1;
        }
        cout<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74