Submission #609312

#	Time	Username	Problem	Language	Result	Execution time	Memory
609312		Redhood	Popeala (CEOI16_popeala)	C++14	0 / 100	40 ms	4824 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[n][t];

    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[i][j] = cur;
        }

    }

    /// yo
    for(int i = 0; i < T; ++i)
        fill(dp[i] , dp[i] + S , inf);
    for(int i = 0; i < t; ++i){
        /// yo
//        cerr << "there " << i << endl;
        vector<int>ps;
        for(int j = 0; j < n; ++j){
            ps.pb(left[j][i]);
        }
        sort(rall(ps));

        for(int k = 1; k <= s; ++k){
            if(i - 1 >= 0 && k >= 2){
                dp[i][k] = min(dp[i][k] , dp[i - 1][k - 1] + score[i]);
            }
            int ptr = 0;
            int cnt = n;
            while(ptr < sz(ps)){
                if(ps[ptr] == -1)
                    break;
                cnt--;
                while(ptr + 1 < sz(ps) && ps[ptr] == ps[ptr+1]){
                    cnt--;
                    ptr++;
                }
                assert(ptr<sz(ps));


                if(ps[ptr]-1 >= 0 && k - 1 >= 0){
//                    cout << " WHATA FUK " << ps[ptr]-1 << ' ' << k-1 << endl;
                    dp[i][k] = min((ll)dp[i][k] , (ll)dp[ps[ptr]-1][k-1] + 1ll * cnt * get(ps[ptr], i));
                }
                int x = (ptr == sz(ps) ? 1 : ps[ptr + 1] + 1);

                if(x <= i && x > 0 && k - 1 >= 0){
//                    cout << " WHATA FUK " << ps[ptr]-1 << ' ' << k-1 << endl;
                    dp[i][k] = min((ll)dp[i][k] , (ll)dp[x-1][k-1] + 1ll * cnt * get(x, i));
                }
                ptr++;
            }
            if(k == 1){
                dp[i][1] = min((ll)dp[i][1], 1ll*cnt*get(0,i));
            }


        }
//        cout << "LOL " << i << '\n';
//        for(int j = 1; j <= 3; ++j)
//            cout << dp[i][j] << ' ';
//        cout << '\n';
    }

    for(int k = 1; k <= s; ++k)
        cout << dp[t - 1][k] << ' ';
    return 0;
}

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