oj.uz

Submission #605989

# Submission time Handle Problem Language Result Execution time Memory
605989 2022-07-26T04:42:00 Z maximath_1 Popeala (CEOI16_popeala) C++11
100 / 100
 262 ms 11340 KB 
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 5;
int n, t, s;
int dp[20005][55], val[20005], pre[20005][55];
string ss[55];
int best[55];

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> t >> s;
	for(int i = 1; i <= t; i ++){
		cin >> val[i];
		val[i] += val[i - 1];
	}
	for(int i = 1; i <= n; i ++){
		cin >> ss[i];
		for(int j = 0; j < t; j ++){
			if(ss[i][j] == '1') pre[j + 1][i] = pre[j][i];
			else pre[j + 1][i] = j + 1;
		}
	}

	for(int i = 1; i <= t; i ++){
		pre[i][0] = i;
		sort(pre[i], pre[i] + n + 1);
	}

	for(int i = 0; i < 20005; i ++)
		for(int j = 0; j < 55; j ++)
			dp[i][j] = inf;
	dp[0][0] = 0;

	for(int i = 1; i <= s; i ++){
		for(int j = 0; j <= n; j ++)
			best[j] = inf;
		for(int j = 1; j <= t; j ++){
			for(int k = 0; k <= n; k ++){
				for(int l = pre[j - 1][k]; l < pre[j][k]; l ++)
					best[k] = min(best[k], dp[l][i - 1] - val[l] * k);
				dp[j][i] = min(dp[j][i], best[k] + val[j] * k);
			}
		}
		cout << dp[t][i] << endl;
	}
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4704 KB Output is correct
2 Correct 9 ms 4692 KB Output is correct
3 Correct 12 ms 4748 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5332 KB Output is correct
2 Correct 53 ms 5588 KB Output is correct
3 Correct 75 ms 5976 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4564 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 12 ms 4704 KB Output is correct
4 Correct 9 ms 4692 KB Output is correct
5 Correct 12 ms 4748 KB Output is correct
6 Correct 40 ms 5332 KB Output is correct
7 Correct 53 ms 5588 KB Output is correct
8 Correct 75 ms 5976 KB Output is correct
9 Correct 70 ms 6816 KB Output is correct
10 Correct 130 ms 7456 KB Output is correct
11 Correct 210 ms 11212 KB Output is correct
12 Correct 241 ms 11332 KB Output is correct
13 Correct 258 ms 11328 KB Output is correct
14 Correct 251 ms 11340 KB Output is correct
15 Correct 262 ms 11336 KB Output is correct