Submission #373560

#	Time	Username	Problem	Language	Result	Execution time	Memory
373560		ijxjdjd	Popeala (CEOI16_popeala)	C++14	26 / 100	2092 ms	17140 KiB

popeala

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXT = 20000;
const int MAXN = 50;
const int MAXS = 50;
const int INF = (int)(2e9+5);
int lzy[4*MAXT];
int seg[4*MAXT][MAXS];
int cst0 = 0;
void upd(int n, int val) {
    FR(i, MAXS) {
        seg[n][i] += val;
    }
    lzy[n] += val;
}
void push(int n) {
    upd(2*n, lzy[n]);
    upd(2*n+1, lzy[n]);
    lzy[n] = 0;
}
void pull(int n) {
    FR(i, MAXS) {
        seg[n][i] = min(seg[2*n][i], seg[2*n+1][i]);
    }
}
void add(int l, int r, int val, int n = 1, int tl = 0, int tr = MAXT-1) {
    if (l > tr || r < tl) {
        return;
    }
    else if (l <= tl && tr <= r) {
        upd(n, val);
    }
    else {
        push(n);
        int tm = (tl + tr)/2;
        add(l, r, val, 2*n, tl, tm);
        add(l, r, val, 2*n+1, tm+1, tr);
        pull(n);
    }
}
void upd(int i, int n = 1, int tl = 0, int tr = MAXT-1) {
    if (tl == tr) {
        if (i == 0) {
        }
        else {
            seg[n][0] = cst0;
            FR(iter, MAXS-1) {
                seg[n][iter+1] = seg[1][iter];
            }
        }
    }
    else {
        int tm = (tl + tr)/2;
        push(n);
        if (i <= tm) {
            upd(i, 2*n, tl, tm);
        }
        else {
            upd(i, 2*n+1, tm+1, tr);
        }
        pull(n);
    }
}
int points[MAXT+1];
int last[MAXN];
bool result[MAXN][MAXT+1];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, T, S;
	cin >> N >> T >> S;
	for (int i = 1; i <= T; i++) {
        cin >> points[i];
	}
	FR(i, 4*MAXT) {
        fill(all(seg[i]), INF);
	}
	for (int i = 0; i < N; i++) {
        last[i] = -1;
        for (int j = 1; j <= T; j++) {
            char c;
            cin >> c;
            result[i][j] = (c == '1');
        }
	}
    for (int i = 0; i < T; i++) {
        upd(i);
        for (int j = 0; j < N; j++) {
            if (last[j] == -1) {
                if (result[j][i+1]) {
                    if (i == 0) {
                        cst0 += points[i+1];
                    }
                    last[j] = i+1;
                    add(i, i, points[i+1]);
                }
            }
            else {
                if (result[j][i+1]) {
                    if (last[j] == 1) {
                        cst0 += points[i+1];
                    }
                    add(last[j]-1, i, points[i+1]);
                }
                else {
                    for (int k = i; k >= last[j]; k--) {
                        add(last[j]-1, k-1, -points[k]);
                        if (last[j] == 1) {
                            cst0 -= points[k];
                        }
                    }
                    last[j] = -1;
                }
            }
        }
    }
    FR(i, S) {
        if (i == 0) {
            cout << cst0 << '\n';
        }
        else {
            cout << seg[1][i-1] << '\n';
        }
    }
	return 0;
}

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