#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 2e4+5;
const int maxt = 55;
int n, t, s;
ll pts[maxn];
ll foo[maxt][maxn];
ll dp[maxt][maxn];
int f(int i, int j)
{
int ans = 0;
for(int p = 1; p<= n; p++)
{
if(foo[p][j]-foo[p][i-1] == j-i+1) ans += pts[j]-pts[i-1];
}
return ans;
}
void solve(int k, int L, int R, int i, int j)
{
if(L> R) return;
int M = (L+R)/2;
pair<ll, int> opt = {2e9, L};
for(int p = max(1, i-10); p<= min(M, j+10); p++)
{
opt = min(opt, {dp[k-1][p-1]+f(p, M), p});
}
dp[k][M] = opt.X;
// printf("dp[%d][%d] = %d\n", k, M, dp[k][M]);
solve(k, L, M-1, i, opt.Y);
solve(k, M+1, R, opt.Y, j);
}
int main()
{
scanf("%d %d %d", &n, &t, &s);
for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
for(int i = 1; i<= t; i++) pts[i] += pts[i-1];
for(int i = 1; i<= n; i++)
{
char bar[maxn]; scanf("%s", bar+1);
for(int j = 1; j<= t; j++) foo[i][j] = bar[j]-'0';
for(int j = 1; j<= t; j++) foo[i][j] += foo[i][j-1];
}
for(int i = 1; i<= t; i++) dp[1][i] = f(1, i);
dp[1][0] = 1e18;
for(int i = 2; i<= s; i++)
{
dp[i][0] = 1e18;
solve(i, 1, t, 1, t);
}
for(int i = 1; i<= s; i++) printf("%lld\n", dp[i][t]);
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:47: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:48:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char bar[maxn]; scanf("%s", bar+1);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
240 ms |
2492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
