oj.uz

Submission #858855

# Submission time Handle Problem Language Result Execution time Memory
858855 2023-10-09T09:24:35 Z Tenis0206 Popeala (CEOI16_popeala) C++11
100 / 100
 949 ms 13088 KB 
#include <bits/stdc++.h>

using namespace std;

const int tmax = 2e4;
const int nmax = 50;
const int oo = INT_MAX;

int n,t,s;
int p[tmax + 5];
int sp[tmax + 5];

char sc[nmax + 5][tmax + 5];

int l[nmax + 5];

int dp[tmax + 5][nmax + 5];

vector<int> vl[tmax + 5];

deque<int> d[nmax + 5];
int last_dr[nmax + 5];

int get_val(int i, int k, int nr)
{
    if(dp[i - 1][k - 1] == oo)
    {
        return oo;
    }
    return dp[i - 1][k - 1] - nr * sp[i - 1];
}

int get_min(int nr, int k, int st, int dr)
{

    for(int i=last_dr[nr]+1;i<=dr;i++)
    {
        while(!d[nr].empty() && get_val(i,k,nr) < get_val(d[nr].back(),k,nr))
        {
            d[nr].pop_back();
        }
        d[nr].push_back(i);
    }
    while(!d[nr].empty() && d[nr].front() < st)
    {
        d[nr].pop_back();
    }
    last_dr[nr] = dr;
    if(d[nr].empty())
    {
        return oo;
    }
    return get_val(d[nr].front(),k,nr);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>t>>s;
    for(int i=1; i<=t; i++)
    {
        cin>>p[i];
        sp[i] = sp[i - 1] + p[i];
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=t; j++)
        {
            cin>>sc[i][j];
        }
    }
    for(int i=0; i<=t; i++)
    {
        for(int k=0; k<=s; k++)
        {
            dp[i][k] = oo;
        }
    }
    for(int i=1; i<=t; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(sc[j][i] == '0')
            {
                l[j] = i;
            }
            vl[i].push_back(l[j]);
        }
        sort(vl[i].begin(),vl[i].end());
        vl[i].push_back(i);
    }
    dp[0][0] = 0;
    for(int k=1; k<=s; k++)
    {
        for(int nr=0;nr<=n;nr++)
        {
            d[nr].clear();
            last_dr[nr] = 0;
        }
        for(int i=k; i<=t; i++)
        {
            int last = 0;
            for(int nr=0; nr<=n; nr++)
            {
                int val = get_min(nr, k, last + 1, vl[i][nr]);
                if(val != oo)
                {
                    val = val + nr * sp[i];
                }
                dp[i][k] = min(dp[i][k], val);
                last = vl[i][nr];
            }
        }
    }
    for(int k=1; k<=s; k++)
    {
        cout<<dp[t][k]<<'\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2904 KB Output is correct
2 Correct 21 ms 2908 KB Output is correct
3 Correct 24 ms 2908 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 3616 KB Output is correct
2 Correct 143 ms 3896 KB Output is correct
3 Correct 176 ms 4184 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 23 ms 2904 KB Output is correct
4 Correct 21 ms 2908 KB Output is correct
5 Correct 24 ms 2908 KB Output is correct
6 Correct 98 ms 3616 KB Output is correct
7 Correct 143 ms 3896 KB Output is correct
8 Correct 176 ms 4184 KB Output is correct
9 Correct 273 ms 5200 KB Output is correct
10 Correct 405 ms 7772 KB Output is correct
11 Correct 793 ms 12928 KB Output is correct
12 Correct 832 ms 12872 KB Output is correct
13 Correct 923 ms 12872 KB Output is correct
14 Correct 949 ms 13088 KB Output is correct
15 Correct 926 ms 12900 KB Output is correct