#include<iostream>
using namespace std;
//using ll = long long;
#define ll int
const ll inf = 1e9 + 123;
const int T = 4e3 + 123;
const int N = 52;
const int S = 52;
ll pref[T];
int cs[N][T];
ll val[T][T];
ll dp[T][S];
void upd(ll &a, ll b) {
a = min(a, b);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, t, s;
cin >> n >> t >> s;
for (int i = 1 ; i <= t ; ++ i) {
cin >> pref[i];
pref[i] += pref[i - 1];
}
for (int i = 1 ; i <= n ; ++ i) {
for (int j = 1 ; j <= t ; ++ j) {
char c; cin >> c;
cs[i][j] = cs[i][j - 1] + (c == '1');
}
}
for (int l = 0 ; l <= t ; ++ l) {
for (int r = l + 1 ; r <= t ; ++ r) {
int cnt = 0;
for (int i = 1 ; i <= n ; ++ i) {
cnt += (cs[i][r] - cs[i][l] == r - l);
}
val[l][r] = cnt * (pref[r] - pref[l]);
}
}
for (int i = 0 ; i <= t ; ++ i) {
for (int x = 0 ; x <= s ; ++ x) {
dp[i][x] = inf;
}
}
dp[0][0] = 0;
for (int i = 1 ; i <= t ; ++ i) {
for (int x = 1 ; x <= s ; ++ x) {
for (int j = 0 ; j < i ; ++ j) {
upd(dp[i][x], dp[j][x-1] + val[j][i]);
}
}
}
for (int i = 1 ; i <= s ; ++ i) {
cout << dp[t][i] << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
3284 KB |
Output is correct |
2 |
Correct |
16 ms |
3244 KB |
Output is correct |
3 |
Correct |
16 ms |
3208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
735 ms |
19696 KB |
Output is correct |
2 |
Correct |
1750 ms |
31488 KB |
Output is correct |
3 |
Execution timed out |
2080 ms |
47948 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
596 KB |
Output is correct |
3 |
Correct |
19 ms |
3284 KB |
Output is correct |
4 |
Correct |
16 ms |
3244 KB |
Output is correct |
5 |
Correct |
16 ms |
3208 KB |
Output is correct |
6 |
Correct |
735 ms |
19696 KB |
Output is correct |
7 |
Correct |
1750 ms |
31488 KB |
Output is correct |
8 |
Execution timed out |
2080 ms |
47948 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |