oj.uz

Submission #134157

# Submission time Handle Problem Language Result Execution time Memory
134157 2019-07-22T07:31:42 Z 임유진(#3231) Popeala (CEOI16_popeala) C++14
100 / 100
 1085 ms 23340 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];

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 < 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 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 i = 1; i <= S; i++) {
		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 = 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 = 1; k <= T; k++) {
				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 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 2 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1528 KB Output is correct
2 Correct 27 ms 1628 KB Output is correct
3 Correct 28 ms 1520 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3336 KB Output is correct
2 Correct 180 ms 4328 KB Output is correct
3 Correct 225 ms 5392 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 29 ms 1528 KB Output is correct
4 Correct 27 ms 1628 KB Output is correct
5 Correct 28 ms 1520 KB Output is correct
6 Correct 126 ms 3336 KB Output is correct
7 Correct 180 ms 4328 KB Output is correct
8 Correct 225 ms 5392 KB Output is correct
9 Correct 292 ms 8028 KB Output is correct
10 Correct 496 ms 10192 KB Output is correct
11 Correct 893 ms 21852 KB Output is correct
12 Correct 927 ms 22096 KB Output is correct
13 Correct 1060 ms 23340 KB Output is correct
14 Correct 1085 ms 23208 KB Output is correct
15 Correct 1041 ms 23180 KB Output is correct