Submission #567585

#	Time	Username	Problem	Language	Result	Execution time	Memory
567585		piOOE	Popeala (CEOI16_popeala)	C++17	0 / 100	611 ms	596 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int S = 51, N = 51, T = 4001, infI = 2e9 + 7;
int pref[T];
const ll infL = 3e18;

int s, n, t, A[T], L[S], R[S], W[S];

bool solved[N][T];

template<typename T>
bool ckmn(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int weight(int l, int r) {
    int every = 0;
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = l; j <= r; ++j) {
            if (!solved[i][j]) {
                sum = 0;
                break;
            }
            sum += A[j];
        }
        every += sum;
    }
    return every;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> t >> s;
    for (int i = 0; i < t; ++i) {
        cin >> A[i];
        pref[i] = pref[i - 1] + A[i];
    }
    for (int i = 0; i < n; ++i) {
        string ss;
        cin >> ss;
        for (int j = 0; j < t; ++j) {
            solved[i][j] = (ss[j] == '1');
        }
    }
    L[0] = 0, R[0] = t - 1, W[0] = weight(0, t - 1);
    cout << W[0] << endl;
    for (int k = 1; k < s; ++k) {
        int prv = accumulate(W, W + k, 0);
        int ans = infI, id_block = -1, id = -1;
        for (int i = 0; i < k; ++i) {
            for (int j = L[i]; j < R[i]; ++j) {
                if (ckmn(ans, prv - W[i] + weight(L[i], j) + weight(j + 1, R[i]))) {
                    id_block = i;
                    id = j;
                }
            }
        }
        assert(ans != infI);
        cout << ans << endl;
        for (int i = id_block + 1; i < k; ++i) {
            W[i + 1] = W[i];
            L[i + 1] = L[i];
            R[i + 1] = R[i];
        }
        W[id_block + 1] = weight(id + 1, R[id_block]);
        L[id_block + 1] = id + 1, R[id_block + 1] = R[id_block];
        W[id_block] = weight(L[id_block], id);
        R[id_block] = id;
    }
    return 0;
}

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