oj.uz

Submission #134155

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

typedef long long lint;
typedef pair<lint, int> pli;

#define fi first
#define se second

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][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++) {
	///if(l == r) for(int j = 0; j <= N; j++) seg[j][idx] = dp[l] - j * sp[l];
		//mkseg(dp[i - 1], 1, 0, T - 1);
		for(int j = 0; j <= N; j++) for(int k = 0; k < T; k++) seg[j][k] = dp[i - 1][k] - j * sp[k];
		//for(int j = 0; j <= N; j++) for(int k = 0; k < T; k++) printf("seg[%d][%d] = %lld\n", j, k, seg[j][k]);
		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 k = 0; k <= N + 1; k++) printf("ch[%d][%d] = %d\n", j, k, ch[j][k]);
		}
		for(int j = 1; j <= T; j++) dp[i][j] = LINF;
		for(int j = 0; j <= N; j++) {
			deque<pli> dq;
			ch[0][j + 1] = 0;
			//for(int k = 0; k < T; k++) printf("seg[%d][%d] = %lld\n", j, k, seg[j][k]);
			for(int k = 1; k <= T; k++) {
				//printf("j = %d, k = %d, ch[k][j] = %d, ch[k][j + 1] = %d\n", j, k, ch[k][j], ch[k][j + 1]);
				for(int l = ch[k - 1][j + 1]; l < ch[k][j + 1]; l++) {
					while(!dq.empty() && dq.back().fi > seg[j][l]) dq.pop_back();
					dq.push_back(make_pair(seg[j][l], l));
				}
				while(!dq.empty() && dq.front().se < ch[k][j]) dq.pop_front();
				if(!dq.empty()) dp[i][k] = min(dp[i][k], dq.front().fi + sp[k] * 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 j = 1; j <= T; 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 77 ms 1528 KB Output is correct
2 Correct 65 ms 1528 KB Output is correct
3 Correct 73 ms 1528 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 3320 KB Output is correct
2 Correct 486 ms 4308 KB Output is correct
3 Correct 590 ms 5500 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 77 ms 1528 KB Output is correct
4 Correct 65 ms 1528 KB Output is correct
5 Correct 73 ms 1528 KB Output is correct
6 Correct 347 ms 3320 KB Output is correct
7 Correct 486 ms 4308 KB Output is correct
8 Correct 590 ms 5500 KB Output is correct
9 Correct 849 ms 8056 KB Output is correct
10 Correct 1309 ms 10708 KB Output is correct
11 Correct 1991 ms 22712 KB Output is correct
12 Execution timed out 2058 ms 23152 KB Time limit exceeded
13 Halted 0 ms 0 KB -