Submission #609338

#	Time	Username	Problem	Language	Result	Execution time	Memory
609338		Redhood	Popeala (CEOI16_popeala)	C++14	17 / 100	2074 ms	5148 KiB

popeala

#include <bits/stdc++.h>
#define fi first
#define se second

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;


typedef long long ll;
typedef long double ld;

const int inf = 2e9 + 1;
const int T = 20'000;
const int S = 51;
int dp[T][S];

int main()
{
    int t, n , s;
    cin >> n >> t >> s;
    vector < int > score(t);
    for(auto &i : score)
    cin >> i;


    vector < string > capble;
    for(int i = 0; i < n; ++i){
        string s;
        cin >> s;
        capble.pb(s);
    }

    vector<int>pref(t);

    pref[0] = score[0];
    for(int i = 1; i < t; ++i){
        pref[i] = pref[i - 1] + score[i];
    }

    auto get = [&](int l , int r){
        assert(l != -1);
        return pref[r] - (l == 0 ? 0 : pref[l - 1]);
    };

    int left[t][n];

    for(int i = 0;i < n; ++i){
        int cur = -1;
        for(int j = 0; j < t; ++j){
            if(capble[i][j] == '0')
                cur = j;
            left[j][i] = cur;
        }

    }

    /// yo
    for(int i = 0; i < T; ++i)
        fill(dp[i] , dp[i] + S , inf);


    int opt[t][s + 1];

    for(int f=0;f<t;++f)
        for(int x=0;x<=s;++x)
            opt[f][x]=0;
    for(int x = 0; x < t; ++x){
        int c = 0;
        for(int f=0;f<n;++f){
            if(left[x][f]==-1)
                c++;
        }
        dp[x][1] = get(0,x) * c;
        opt[x][1] = 0;
    }



    for(int j = 2; j <= s; ++j){
        for(int i = t - 1; i >= 0; --i){

            if(i+1<j){
                continue;
            }
            int l = max(opt[i][j - 1],j-1-1), r = (i == t - 1 ? i-1 : opt[i + 1][j]);
            r = min(r , i - 1);
            l = j-2, r = i-1;

            if(l > r) {
                cout << "whata fuk " << i << ' '<<j << ' ' << l << ' ' << r << '\n';
                exit(0);
            }

            int ans = inf;
            int pr = -1;
            for(int cand = l; cand <= r; ++cand){
                if(dp[cand][j - 1] != inf){
                    int cost = dp[cand][j - 1];
                    int c = 0;
                    for(int f=0;f<n;++f){
                        if(left[i][f] <= cand)
                            c++;
                    }
                    cost += c * get(cand+1, i);
                    if(cost < ans){
                        ans = cost;
                        pr = cand;
                    }
                }
            }
            opt[i][j] = pr;
            dp[i][j] = ans;
        }
    }
    for(int k = 1; k <= s; ++k)
        cout << dp[t-1][k] << ' ' << '\n';
    return 0;
}

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