Submission #1212600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212600		MMihalev	Popeala (CEOI16_popeala)	C++20	100 / 100	481 ms	32236 KiB

popeala

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N=5e1+5;
const int MAX_T=2e4+4;
const int INF=2e9+69;
int n,t,s;
int points[MAX_T];
bool test[MAX_N][MAX_T];
vector<pair<int,int>>intervals[MAX_T];
vector<pair<int,int>>leftends[MAX_T];
int sum[MAX_T];
int dp[MAX_T][MAX_N];
void precompute()
{
    for(int guy=1;guy<=n;guy++)
    {
        int cons=0;

        for(int i=1;i<=t;i++)
        {
            if(test[guy][i]==1)cons++;
            else cons=0;

            if(cons)
            {
                sum[i]++;
                leftends[i].push_back({cons,guy});
            }
        }
    }

    for(int i=1;i<=t;i++)
    {
        if(leftends[i].size()==0)continue;

        sort(leftends[i].begin(),leftends[i].end());

        int last=leftends[i][0].first;
        int cur_sum=1;

        for(int j=1;j<leftends[i].size();j++)
        {
            if(last==leftends[i][j].first)
            {
                cur_sum++;
            }
            else
            {
                intervals[i].push_back({i-last,sum[i]});
                sum[i]-=cur_sum;
                cur_sum=1;
                last=leftends[i][j].first;
            }
        }
        intervals[i].push_back({i-last,sum[i]});
    }
}
int p[MAX_T][MAX_N];
void solve()
{
    for(int i=0;i<=t;i++)
    {
        for(int k=0;k<=s;k++)
        {
            dp[i][k]=INF;
        }
    }
    dp[0][0]=0;

    int k,x,i;

    for(k=1;k<=s;++k)
    {
        for(x=0;x<=n;++x)
        {
            p[0][x]=dp[0][k-1]-x*points[0];
            for(i=1;i<=t;++i)
            {
                p[i][x]=min(dp[i][k-1]-x*points[i],p[i-1][x]);
            }
        }

        for(i=1;i<=t;++i)
        {
            int zero=i,prevlast=i;

            for(auto&[last,cost]:intervals[i])
            {
                zero=last;
                dp[i][k]=min(dp[i][k],p[prevlast-1][cost]+cost*points[i]);
                prevlast=last;
            }

            if(zero>0)dp[i][k]=min(dp[i][k],p[zero-1][0]);
        }
    }

    for(int k=1;k<=s;k++)
    {
        cout<<dp[t][k]<<"\n";
    }
}
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    #ifdef ONLINE_JUDGE
    freopen("popeala.in", "r", stdin);
    freopen("popeala.out", "w", stdout);
    #endif

    cin>>n>>t>>s;

    for(int i=1;i<=t;i++)
    {
        cin>>points[i];
        points[i]+=points[i-1];
    }

    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        for(int j=0;j<t;j++)
        {
            if(s[j]=='0')test[i][j+1]=0;
            else test[i][j+1]=1;
        }
    }

    precompute();

    solve();

    return 0;
}

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