oj.uz

Submission #134133

# Submission time Handle Problem Language Result Execution time Memory
134133 2019-07-22T06:28:11 Z 임유진(#3231) Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 10220 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[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++) {
			dp[i][j] = LINF;
			for(int k = 0; k < N; k++) ch[k] = *prev(upper_bound(wro[k].begin(), wro[k].end(), j));
			ch[N] = 0;
			ch[N + 1] = j;
			sort(ch, ch + N + 2);
			/*
			printf("ch : ");
			for(int k = 0; k <= N + 1; k++) printf("%d ", ch[k]);
			printf("\n");
			*/
			for(int k = 0; k <= N; k++)
				dp[i][j] = min(dp[i][j], gseg(seg[k], 1, 0, T - 1, ch[k], ch[k + 1] - 1) + sp[j] * k);

			//for(int k = j; k > 0; k--) 
				//dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + (sp[j] - sp[k - 1]) * cnt[k][j]);
			//printf("dp[%d][%d] = %lld\n", i, j, dp[i][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 166 ms 1696 KB Output is correct
2 Correct 145 ms 1820 KB Output is correct
3 Correct 159 ms 1736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 5264 KB Output is correct
2 Correct 1558 ms 6016 KB Output is correct
3 Correct 1987 ms 6428 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 166 ms 1696 KB Output is correct
4 Correct 145 ms 1820 KB Output is correct
5 Correct 159 ms 1736 KB Output is correct
6 Correct 1046 ms 5264 KB Output is correct
7 Correct 1558 ms 6016 KB Output is correct
8 Correct 1987 ms 6428 KB Output is correct
9 Execution timed out 2017 ms 10220 KB Time limit exceeded
10 Halted 0 ms 0 KB -