#include <bits/stdc++.h>
using namespace std;
const int MAXT = 2e4+10;
const int MAXN = 50+10;
const int MAXS = 50+10;
const int INF = 2e9+10;
int N, T, S;
int val[MAXT], valp[MAXT];
int dp[MAXT][MAXS];
vector<string> res;
int pf[MAXN][MAXT];
int score(int l, int r) {
int subtask_score = valp[r] - valp[l-1];
int ret = 0;
for(int i=1;i<=N;i++) {
if(pf[i][r] - pf[i][l-1] == (r-l+1)) ret += subtask_score;
}
//printf("%d %d per subtask:%d, total=%d\n", l, r, subtask_score, ret);
return ret;
}
int solve(int i, int k) {
if(k==0 && i>0) return INF;
if(k>i) return INF;
if(i==0 && k==0) return 0;
if(dp[i][k] != -1) return dp[i][k];
dp[i][k] = INF;
for(int j=1;j<=i;j++) {
dp[i][k] = min(dp[i][k], solve(j-1, k-1) + score(j, i));
}
return dp[i][k];
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> T >> S;
for(int i=1;i<=T;i++) {
cin >> val[i];
valp[i] = valp[i-1] + val[i];
}
res.assign(N+1, "");
for(int i=1;i<=N;i++) {
cin >> res[i];
for(int j=1;j<=T;j++) {
pf[i][j] = pf[i][j-1] + (res[i][j-1]=='1');
}
}
for(int i=1;i<=T;i++) {
for(int k=0;k<=S;k++) {
dp[i][k] = INF;
}
}
for(int k=1;k<=S;k++) {
for(int i=1;i<=T;i++) {
for(int j=k-1;j<i;j++) {
//printf("i=%d, k=%d, j=%d\n", i, j, k);
dp[i][k] = min(dp[i][k], dp[j][k-1] + score(j+1, i));
}
}
}
for(int k=1;k<=S;k++) {
printf("%d\n", dp[T][k]);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
11720 KB |
Output is correct |
2 |
Correct |
0 ms |
11720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
11720 KB |
Output is correct |
2 |
Correct |
433 ms |
11720 KB |
Output is correct |
3 |
Correct |
499 ms |
11720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2000 ms |
11852 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
11720 KB |
Output is correct |
2 |
Correct |
0 ms |
11720 KB |
Output is correct |
3 |
Correct |
439 ms |
11720 KB |
Output is correct |
4 |
Correct |
433 ms |
11720 KB |
Output is correct |
5 |
Correct |
499 ms |
11720 KB |
Output is correct |
6 |
Execution timed out |
2000 ms |
11852 KB |
Execution timed out |
7 |
Halted |
0 ms |
0 KB |
- |