제출 #1307071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307071		HoriaHaivas	조교 (CEOI16_popeala)	C++20	100 / 100	600 ms	46464 KiB

popeala

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


bool got[55][20005];
int score[20005];
int dp[20005][55];
int prefmin[55][20005];
int sp[20005];
int banned[55];
int last[55];
pair<int,int> er[20005][55];
vector<int> vals[20005];
int n;
const int inf=1e10;


int count_rows(int l, int r)
{
    int re,pas;
    re=0;
    pas=(1<<5);
    while (pas)
    {
        if (re+pas<vals[r].size() && vals[r][re+pas]<l)
            re+=pas;
        pas=pas/2;
    }
    if (vals[r][re]<l)
        return re+1;
    else
        return 0;
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,s,i,j,k,ceva,previ,r,sum,finished,x,pas;
    bool ok;
    string nush;
    cin >> n >> t >> s;
    for (i=1; i<=t; i++)
        cin >> score[i];
    sp[0]=0;
    for (i=1; i<=t; i++)
        sp[i]=sp[i-1]+score[i];
    for (i=1; i<=n; i++)
    {
        cin >> nush;
        for (j=0; j<nush.size(); j++)
        {
            if (nush[j]=='0')
                got[i][j+1]=0;
            else
                got[i][j+1]=1;
        }
    }
    for (i=1; i<=t; i++)
    {
        for (k=1; k<=n; k++)
        {
            if (!got[k][i])
                last[k]=i;
            vals[i].push_back(last[k]);
        }
        sort(vals[i].begin(),vals[i].end());
    }
    for (i=1; i<=t; i++)
    {
        for (j=1; j<=s; j++)
            dp[i][j]=inf;
    }
    for (i=0; i<=t; i++)
    {
        for (j=0; j<=n; j++)
        {
            prefmin[j][i]=inf;
        }
    }
    dp[0][0]=0;
    sum=0;
    for (i=1; i<=t; i++)
    {
        for (k=1; k<=n; k++)
        {
            if (banned[k])
                continue;
            if (!got[k][i])
            {
                sum-=sp[i-1];
                banned[k]=1;
            }
            else
                sum+=score[i];
        }
        dp[i][1]=sum;
    }
    for (i=1; i<=t; i++)
    {
        for (x=0; x<=n; x++)
        {
            er[i][x].first=-1;
            er[i][x].second=0;
        }
    }
    for (j=2; j<=s; j++)
    {
        for (x=0; x<=n; x++)
        {
            prefmin[x][0]=inf;
            for (i=1; i<=t; i++)
                prefmin[x][i]=min(prefmin[x][i-1],dp[i][j-1]-sp[i]*x);
        }
        for (i=1; i<=t; i++)
        {
            for (x=n; x>=0; x--)
            {
                if (er[i][x].first==-1)
                {
                    r=i;
                    pas=(1<<14);
                    while (pas)
                    {
                        if (r-pas>=0 && count_rows(r-pas+1,i)>x)
                            r-=pas;
                        pas=pas/2;
                    }
                    er[i][x].first=r;
                    if (r!=0 && count_rows(r,i)==x)
                    {
                        dp[i][j]=min(dp[i][j],prefmin[x][r-1]+sp[i]*x);
                        er[i][x].second=1;
                    }
                }
                else
                {
                    if (er[i][x].second==1)
                    {
                        r=er[i][x].first;
                        dp[i][j]=min(dp[i][j],prefmin[x][r-1]+sp[i]*x);
                    }
                }
            }
        }
    }
    for (j=1; j<=s; j++)
        cout << dp[t][j] << "\n";
    return 0;
}

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