oj.uz

Submission #564220

# Submission time Handle Problem Language Result Execution time Memory
564220 2022-05-18T18:36:23 Z Rafi22 Popeala (CEOI16_popeala) C++14
100 / 100
 776 ms 18872 KB 
#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>>s>>t;
    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]*(ll)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]*(ll)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]*(ll)c);
                }
                V.pop_back();
            }
            reverse(all(V1));
            V=V1;
        }
        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]*(ll)l);
        }
    }
    for(int i=1;i<=t;i++) cout<<DP[i][s]<<endl;


    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1116 KB Output is correct
2 Correct 23 ms 1148 KB Output is correct
3 Correct 20 ms 1212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2628 KB Output is correct
2 Correct 117 ms 3404 KB Output is correct
3 Correct 183 ms 4392 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 24 ms 1116 KB Output is correct
4 Correct 23 ms 1148 KB Output is correct
5 Correct 20 ms 1212 KB Output is correct
6 Correct 78 ms 2628 KB Output is correct
7 Correct 117 ms 3404 KB Output is correct
8 Correct 183 ms 4392 KB Output is correct
9 Correct 236 ms 6772 KB Output is correct
10 Correct 306 ms 8504 KB Output is correct
11 Correct 742 ms 18268 KB Output is correct
12 Correct 743 ms 18740 KB Output is correct
13 Correct 746 ms 18676 KB Output is correct
14 Correct 776 ms 18872 KB Output is correct
15 Correct 742 ms 18728 KB Output is correct