Submission #564217

#	Time	Username	Problem	Language	Result	Execution time	Memory
564217		Rafi22	Popeala (CEOI16_popeala)	C++14	0 / 100	4 ms	1492 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

ll DP[57][20007];
ll mn[57][20007];
string is[57];
ll a[20007];
ll suf[20007];
bool was[57];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,t,s;
    cin>>n>>t>>s;
    for(int i=1;i<=s;i++) cin>>a[i];
    for(int i=s;i>0;i--) suf[i]=suf[i+1]+a[i];
    for(int i=1;i<=n;i++) cin>>is[i];
    for(int l=0;l<=n;l++)
    {
        for(int i=0;i<=s;i++) mn[l][i]=suf[1]*l;
    }
    for(int j=1;j<=t;j++)
    {
        vector<pair<int,int>>V;
        for(int i=1;i<=s;i++)
        {
            for(int l=1;l<=n;l++) if(is[l][i-1]=='0') V.pb({i,l});
            vector<pair<int,int>>V1;
            int c=n;
            for(int l=1;l<=n;l++) was[l]=0;
            DP[j][i]=infl;
            DP[j][i]=min(DP[j][i],mn[c][i-1]-suf[i+1]*c);
            while(sz(V)>0)
            {
                if(!was[V.back().nd])
                {
                    was[V.back().nd]=1;
                    V1.pb(V.back());
                    c--;
                    DP[j][i]=min(DP[j][i],mn[c][V.back().st-1]-suf[i+1]*c);
                }
                V.pop_back();
            }
          //  cout<<DP[j][i]<<" ";
            reverse(all(V1));
            V=V1;
        }
        //cout<<endl;
        for(int l=0;l<=n;l++)
        {
            mn[l][0]=infl;
            for(int i=1;i<=s;i++) mn[l][i]=min(mn[l][i-1],DP[j][i]+suf[i+1]*l);
        }
    }
    for(int i=1;i<=t;i++) cout<<DP[i][s]<<endl;


    return 0;
}

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