oj.uz

Submission #609931

# Submission time Handle Problem Language Result Execution time Memory
609931 2022-07-28T03:22:22 Z maximath_1 Popeala (CEOI16_popeala) C++11
100 / 100
 276 ms 10320 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 2 ms 4692 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 9 ms 4692 KB Output is correct
2 Correct 9 ms 4692 KB Output is correct
3 Correct 10 ms 4692 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5232 KB Output is correct
2 Correct 53 ms 5460 KB Output is correct
3 Correct 54 ms 5716 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4692 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 9 ms 4692 KB Output is correct
4 Correct 9 ms 4692 KB Output is correct
5 Correct 10 ms 4692 KB Output is correct
6 Correct 39 ms 5232 KB Output is correct
7 Correct 53 ms 5460 KB Output is correct
8 Correct 54 ms 5716 KB Output is correct
9 Correct 79 ms 6460 KB Output is correct
10 Correct 120 ms 6996 KB Output is correct
11 Correct 200 ms 10192 KB Output is correct
12 Correct 189 ms 10320 KB Output is correct
13 Correct 276 ms 10320 KB Output is correct
14 Correct 255 ms 10268 KB Output is correct
15 Correct 259 ms 10268 KB Output is correct