제출 #1306373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306373		HoriaHaivas	Popeala (CEOI16_popeala)	C++20	17 / 100	1558 ms	9284 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);
}


struct operatie
{
    int l;
    int r;
    int x;
};

bool got[55][20005];
int score[55];
int dp[20005][55];
int dp2[20005][55];
vector<operatie> st[55];
pair<int,int> interval[55];
const int inf=1e10;

struct Node
{
    int minval;
    int lazy;
};

class AINT
{
public:
    Node aint[80005];

    void build(int l, int r, int val)
    {
        if (l==r)
        {
            aint[val].minval=0;
            aint[val].lazy=0;
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2);
        build(mid+1,r,val*2+1);
        aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
        aint[val].lazy=0;
    }

    void prop(int val, int l, int r)
    {
        if (aint[val].lazy==0)
            return;
        aint[val].minval+=aint[val].lazy;
        if (l!=r)
        {
            aint[val*2].lazy+=aint[val].lazy;
            aint[val*2+1].lazy+=aint[val].lazy;
        }
        aint[val].lazy=0;
    }

    void lazy_update(int l, int r, int val, int qa, int qb, int x)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            aint[val].lazy+=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (qa<=mid)
            lazy_update(l,mid,val*2,qa,qb,x);
        if (qb>mid)
            lazy_update(mid+1,r,val*2+1,qa,qb,x);
        prop(val*2,l,mid);
        prop(val*2+1,mid+1,r);
        aint[val].minval=min(aint[val*2].minval,aint[val*2+1].minval);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            return aint[val].minval;
        }
        int mid,ans;
        ans=inf;
        mid=(l+r)/2;
        if (qa<=mid)
            ans=min(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=min(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }
} aint[55];


int sum(int l, int r)
{
    int ans,i;
    ans=0;
    for (i=l; i<=r; i++)
    {
        ans+=score[i];
    }
    return ans;
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t,n,s,i,j,k,ceva,previ,l;
    bool ok;
    string nush;
    cin >> n >> t >> s;
    for (i=1; i<=t; i++)
        cin >> 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<=s; i++)
    {
        aint[i].build(1,t,1);
        if (i!=1)
            aint[i].lazy_update(1,t,1,1,i-1,inf);
    }
    for (i=1; i<=n; i++)
    {
        interval[i].first=0;
        interval[i].second=0;
    }
    for (j=1; j<=s; j++)
    {
        for (i=1; i<=t; i++)
        {
            for (k=1; k<=n; k++)
            {
                if (got[k][i]==0)
                {
                    ///sterge i intervalul
                    if (interval[k].first!=0 && interval[k].second!=0)
                    {
                        interval[k].first=0;
                        interval[k].second=0;
                    }
                    while (!st[k].empty())
                    {
                        aint[j].lazy_update(1,t,1,st[k].back().l,st[k].back().r,-st[k].back().x);
                        st[k].pop_back();
                    }
                }
                else
                {
                    ///ajusteaza i intervalul
                    if (interval[k].first==0 && interval[k].second==0)
                    {
                        interval[k].first=i;
                        interval[k].second=i;
                    }
                    else
                    {
                        interval[k].second++;
                    }
                    st[k].push_back({interval[k].first,interval[k].second,score[i]});
                    aint[j].lazy_update(1,t,1,interval[k].first,interval[k].second,score[i]);
                }
            }
            if (j!=1)
            dp[i][j]=aint[j].query(1,t,1,1,i);
            else
            dp[i][j]=aint[j].query(1,t,1,1,1);
            if (i+1<=t)
            aint[j+1].lazy_update(1,t,1,i+1,i+1,dp[i][j]);
        }
        for (k=1;k<=n;k++)
        {
             st[k].clear();
             interval[k].first=0;
             interval[k].second=0;
        }
    }
    for (i=1; i<=s; i++)
        cout << dp[t][i] << "\n";
    /*
    for (i=0; i<=t; i++)
    {
        for (j=0; j<=s; j++)
        {
            dp2[i][j]=inf;
        }
    }
    dp2[0][0]=0;
    for (i=1; i<=t; i++)
    {
        for (j=1; j<=s; j++)
        {
            for (previ=0; previ<i; previ++)
            {
                ceva=0;
                for (k=1; k<=n; k++)
                {
                    ok=true;
                    for (l=previ+1; l<=i; l++)
                    {
                        if (!got[k][l])
                            ok=false;
                    }
                    if (ok)
                        ceva+=sum(previ+1,i);
                }
                dp2[i][j]=min(dp2[i][j],dp2[previ][j-1]+ceva);
            }
        }
    }
    for (i=1; i<=s; i++)
        cout << dp2[t][i] << "\n";
    */
    return 0;
}

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