oj.uz

Submission #134147

# Submission time Handle Problem Language Result Execution time Memory
134147 2019-07-22T07:04:32 Z 임유진(#3231) Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 11404 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;

const int INF = 1 << 30;
const lint LINF = 1ll << 32;
const int MAXN = 55;
const int MAXT = 20005;

int N, T, S;
int P[MAXT];
char R[MAXN][MAXT];
int sp[MAXT];
lint dp[MAXN][MAXT];
lint seg[MAXN][2 * MAXT];
vector<int> wro[MAXN];
int ch[MAXT][MAXN];

void mkseg(lint dp[], int idx, int l, int r) {
	if(l == r) for(int j = 0; j <= N; j++) seg[j][idx] = dp[l] - j * sp[l];
	else {
		int m = (l + r) / 2;
		mkseg(dp, idx * 2, l, m);
		mkseg(dp, idx * 2 + 1, m + 1, r);
		for(int j = 0; j <= N; j++) seg[j][idx] = min(seg[j][idx * 2], seg[j][idx * 2 + 1]);
	}
}

lint gseg(lint seg[], int idx, int l, int r, int x, int y) {
	//if(idx == 1) printf("gseg(x = %d, y = %d)\n", x, y);
	if(x <= l && r <= y) return seg[idx];
	if(r < x || y < l) return LINF;
	int m = (l + r) / 2;
	return min(gseg(seg, idx * 2, l, m, x, y), gseg(seg, idx * 2 + 1, m + 1, r, x, y));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> N >> T >> S;
	for(int i = 1; i <= T; i++) cin >> P[i];
	for(int i = 0; i < N; i++) cin >> R[i];

	for(int i = 1; i <= T; i++) sp[i] = sp[i - 1] + P[i];
	//for(int i = 0; i <= T; i++) printf("%d ", sp[i]);
	//printf("\n");
	for(int i = 0; i < N; i++) {
		wro[i].push_back(0);
		for(int j = 0; j < T; j++) if(R[i][j] == '0') wro[i].push_back(j + 1);
	}
	for(int i = 1; i <= S; i++) dp[i][0] = LINF;
	for(int i = 1; i <= T; i++) dp[0][i] = LINF;
	for(int i = 1; i <= S; i++) {
		mkseg(dp[i - 1], 1, 0, T - 1);
		/*
		for(int j = 0; j <= N; j++) {
			for(int k = 1; k <= 5; k++) printf("%lld ", seg[j][k]);
			printf("\n");
		}
		*/
		for(int j = 1; j <= T; j++) {
			for(int k = 0; k < N; k++) ch[j][k] = *prev(upper_bound(wro[k].begin(), wro[k].end(), j));
			ch[j][N] = 0;
			ch[j][N + 1] = j;
			sort(ch[j], ch[j] + N + 2);
		}
		for(int j = 1; j <= T; j++) dp[i][j] = LINF;
		for(int j = 0; j <= N; j++) {
			for(int k = 1; k <= T; k++)
				dp[i][k] = min(dp[i][k], gseg(seg[j], 1, 0, T - 1, ch[k][j], ch[k][j + 1] - 1) + sp[k] * j);
		}
	}

	for(int i = 1; i <= S; i++) cout << dp[i][T] << "\n";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 1804 KB Output is correct
2 Correct 159 ms 1784 KB Output is correct
3 Correct 174 ms 1784 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 5752 KB Output is correct
2 Correct 1480 ms 6520 KB Output is correct
3 Correct 1905 ms 7124 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 179 ms 1804 KB Output is correct
4 Correct 159 ms 1784 KB Output is correct
5 Correct 174 ms 1784 KB Output is correct
6 Correct 996 ms 5752 KB Output is correct
7 Correct 1480 ms 6520 KB Output is correct
8 Correct 1905 ms 7124 KB Output is correct
9 Execution timed out 2069 ms 11404 KB Time limit exceeded
10 Halted 0 ms 0 KB -