#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int T = 4001;
const int N = 51;
const int S = 51;
const int INF = 2e9 + 10;
int n, t, s, p[T], dp[S][T], sumP[T], sumA[N][T], cost[T][T];
string a[N];
void ReadInput(){
cin >> n >> t >> s;
for(int i = 1; i <= t; i++)
cin >> p[i];
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] = '*' + a[i];
}
}
int Cost(int l, int r){
int sum = sumP[r] - sumP[l - 1], cnt = 0;
for(int i = 1; i <= n; i++)
cnt += (sumA[i][r] - sumA[i][l - 1] == r - l + 1);
return sum * cnt;
}
void Solve(){
for(int i = 1; i <= t; i++)
sumP[i] = sumP[i - 1] + p[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= t; j++)
sumA[i][j] = sumA[i][j - 1] + (a[i][j] == '1');
for(int i = 1; i <= t; i++)
for(int j = i; j <= t; j++)
cost[i][j] = Cost(i, j);
for(int i = 1; i <= t; i++)
dp[1][i] = Cost(1, i);
for(int i = 2; i <= s; i++)
for(int j = i; j <= t; j++){
dp[i][j] = INF;
for(int k = i; k <= j; k++)
dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + cost[k][j]);
}
for(int i = 1; i <= s; i++)
cout << dp[i][t] << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ReadInput();
Solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
3456 KB |
Output is correct |
2 |
Correct |
20 ms |
3692 KB |
Output is correct |
3 |
Correct |
18 ms |
3436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1109 ms |
20076 KB |
Output is correct |
2 |
Execution timed out |
2086 ms |
31988 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
748 KB |
Output is correct |
3 |
Correct |
18 ms |
3456 KB |
Output is correct |
4 |
Correct |
20 ms |
3692 KB |
Output is correct |
5 |
Correct |
18 ms |
3436 KB |
Output is correct |
6 |
Correct |
1109 ms |
20076 KB |
Output is correct |
7 |
Execution timed out |
2086 ms |
31988 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |