oj.uz

Submission #373560

# Submission time Handle Problem Language Result Execution time Memory
373560 2021-03-05T05:25:17 Z ijxjdjd Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 17140 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15980 KB Output is correct
2 Correct 17 ms 16108 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 16236 KB Output is correct
2 Correct 160 ms 16236 KB Output is correct
3 Correct 165 ms 16384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 16620 KB Output is correct
2 Correct 1020 ms 16748 KB Output is correct
3 Correct 1403 ms 16976 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15980 KB Output is correct
2 Correct 17 ms 16108 KB Output is correct
3 Correct 179 ms 16236 KB Output is correct
4 Correct 160 ms 16236 KB Output is correct
5 Correct 165 ms 16384 KB Output is correct
6 Correct 699 ms 16620 KB Output is correct
7 Correct 1020 ms 16748 KB Output is correct
8 Correct 1403 ms 16976 KB Output is correct
9 Execution timed out 2092 ms 17140 KB Time limit exceeded
10 Halted 0 ms 0 KB -