#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const double eps = 1e-9;
const double pi = 3.141592653589793238462;
const int inf = 2e9 + 10;
#define MAX_T 20005
int N, T, S;
int pts[MAX_T];
int res[55][MAX_T];
int dp[55][MAX_T];
int P[55][MAX_T];
char str[MAX_T];
int cost(int i, int j) {
// if (i > j) return 200000000;
if (i > j) return 0;
int cnt = 0;
for (int st = 1; st <= N; st++)
cnt += (res[st][j] - res[st][i-1] == j - i + 1);
//printf("for (%d, %d) cnt = %d and cost = %d\n", i, j, cnt, cnt * (pts[j] - pts[i-1]));
return cnt * (pts[j] - pts[i-1]);
}
void solve(int k, int l1, int l2, int p1, int p2) {
if (l1 > l2) return;
int lm = (l1 + l2) >> 1;
dp[k][lm] = inf;
P[k][lm] = -1;
for (int z = p1; z <= p2; z++) {
if (z >= lm) break;
int cur = dp[k-1][z] + cost(z+1, lm);
if (cur < dp[k][lm]) {
dp[k][lm] = cur;
P[k][lm] = z;
}
}
//printf("ans for pos %d (%d) is at pos %d of previous (j-1) dp\n", lm, k, P[k][lm]);
if (P[k][lm] == -1) {
solve(k, l1, lm - 1, p1, p2);
solve(k, lm + 1, l2, p1, p2);
}
solve(k, l1, lm-1, p1, P[k][lm]);
solve(k, lm+1, l2, P[k][lm], p2);
}
int main() {
//freopen("popeala.in", "rt", stdin);
//freopen("popeala.out", "wt", stdout);
scanf("%d %d %d", &N, &T, &S);
for (int i = 1; i <= T; i++) {
scanf("%d", &pts[i]);
pts[i] += pts[i-1];
}
for (int i = 1; i <= N; i++) {
scanf(" %s", str+1);
for (int j = 1; j <= T; j++)
res[i][j] = res[i][j-1] + (str[j] == '1');
}
// for K = 1
for (int i = 1; i <= T; i++)
dp[1][i] = cost(1, i);
printf("%d\n", dp[1][T]);
/*
for (int j = 2; j <= S; j++) {
for (int i = 1; i <= T; i++) {
dp[j][i] = inf;
for (int k = j-1; k < i; k++)
dp[j][i] = min(dp[j][i], dp[j-1][k] + cost(k+1, i));
}
printf("%d\n", dp[j][T]);
}
*/
for (int k = 2; k <= S; k++) {
solve(k, k, T, k - 1, T);
printf("%d\n", dp[k][T]);
}
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &N, &T, &S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &pts[i]);
~~~~~^~~~~~~~~~~~~~~
popeala.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", str+1);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
2300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
