#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int len = 2e4+5;
const ll inf = 1e15;
int po[len], can[55][len], n, s, t;
ll dp[55][len];
ii inter[55][len];
deque<pair<ll, int> > deq;
int val(int l, int r){
int ans = 0;
for (int i = 1; i <= n; i++)
if (can[i][r]-can[i][l-1] == r-l+1)
ans += po[r]-po[l-1];
return ans;
}
int cnt(int l, int r){
int ans = 0;
for (int i = 1; i <= n; i++)
if (can[i][r]-can[i][l-1] == r-l+1)
ans++;
return ans;
}
ll fin_mn(int rem, int x, int l, int r){
ll ans = inf;
for (int i = l; i <= r; i++)
ans = min(ans, x*po[i] + dp[rem][i+1]);
return ans;
}
/*int bs(int i, int x){
int l = i, r = t, ans = -1;
while (l <= r){
int mid = (l+r)/2;
if (val(i, mid) <= x*(po[mid]-po[i-1])){
ans = mid;
r = mid-1;
}
else
l = mid+1;
}
return ans;
}
ll solve(int i, int rem){
if (i == t+1 && rem == 0) return 0;
if (i == t+1 && rem != 0) return inf;
if (rem == 1) return val(i, t);
if (dp[i][rem] != -1) return dp[i][rem];
ll ans = inf;
//for (int j = i; j <= t; j++)
// ans = min(ans, val(i, j) + solve(j+1, rem-1));
for (int x = 0; x <= n; x++){
int j = bs(i, x);
//printf("i = %d, x = %d, j = %d\n", i, x, j);
if (j != -1 && val(i, j) == x*(po[j]-po[i-1]))
ans = min(ans, solve(j+1, rem-1) + val(i, j));
}
//printf("i = %d, rem = %d, ans = %lld\n", i, rem, ans);
return dp[i][rem] = ans;
}*/
int main(){
scanf("%d %d %d", &n, &t, &s);
for (int i = 1; i <= t; i++)
scanf("%d", &po[i]);
for (int i = 1; i <= n; i++){
scanf(" ");
for (int j = 1; j <= t; j++){
char temp;
scanf("%c", &temp);
if (temp == '1')
can[i][j] = 1;
}
}
/*for (int i = 1; i <= n; i++){
for (int j = 1; j <= t; j++)
printf("%d", can[i][j]);
printf("\n");
}*/
for (int j = 1; j <= t; j++)
po[j] += po[j-1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= t; j++)
can[i][j] += can[i][j-1];
//for (int i = 1; i <= t; i++)
// for (int j = 0; j <= s; j++)
// dp[i][j] = -1;
//for (int i = 1; i <= t; i++)
// for (int j = i; j <= t; j++)
// printf("(%d, %d) = %d\n", i, j, val(i, j));
for (int x = 0; x <= n; x++){
for (int i = 1, l = 1, r = 1; i <= t; i++){
l = max(l, i), r = max(r, i);
while (l <= t && cnt(i, l) > x) l++;
while (r <= t && cnt(i, r) >= x) r++;
//printf("x = %d, i = %d, l = %d, r = %d\n", x, i, l, r-1);
inter[x][i] = mp(l, r);
}
}
for (int rem = 1; rem <= s; rem++)
for (int i = 1; i <= t+1; i++)
dp[rem][i] = inf;
for (int i = 1; i <= t; i++)
dp[1][i] = val(i, t);
//for (int i = 1; i <= t; i++)
// printf("rem = 1, i = %d, ans = %lld\n", i, dp[1][i]);
for (int rem = 2; rem <= s; rem++){
for (int x = 0; x <= n; x++){
deq.clear();
int cur = 1;
for (int i = 1; i <= t; i++){
//printf("ans before is: %lld\n", dp[rem][i]);
int l = inter[x][i].fi, r = inter[x][i].se;
cur = max(cur, l);
while (!deq.empty() && deq.front().se < l)
deq.pop_front();
while (cur < r){
ll val = dp[rem-1][cur+1] + x*po[cur];
while (!deq.empty() && val <= deq.back().fi)
deq.pop_back();
deq.push_back(mp(val, cur++));
}
if (!deq.empty())
dp[rem][i] = min(dp[rem][i], deq.front().fi - x*po[i-1]);
//if (l >= i && fin_mn(rem-1, x, l, r-1) != inf)
// dp[rem][i] = min(dp[rem][i], fin_mn(rem-1, x, l, r-1) - x*po[i-1]);
//printf("rem = %d, x = %d, i = %d, l = %d, r = %d, ans = %lld\n", rem, x, i, l, r-1, dp[rem][i]);
}
}
}
for (int rem = 1; rem <= s; rem++)
printf("%lld\n", dp[rem][1]);
return 0;
}
/*
2 5 5
2 1 3 5 6
10010
11011
*/
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:80:10: 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:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &po[i]);
~~~~~^~~~~~~~~~~~~~
popeala.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" ");
~~~~~^~~~~
popeala.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &temp);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
1564 KB |
Output is correct |
| 2 |
Correct |
31 ms |
1564 KB |
Output is correct |
| 3 |
Correct |
32 ms |
1768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
3312 KB |
Output is correct |
| 2 |
Correct |
201 ms |
4128 KB |
Output is correct |
| 3 |
Correct |
301 ms |
5236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
748 KB |
Output is correct |
| 3 |
Correct |
44 ms |
1564 KB |
Output is correct |
| 4 |
Correct |
31 ms |
1564 KB |
Output is correct |
| 5 |
Correct |
32 ms |
1768 KB |
Output is correct |
| 6 |
Correct |
163 ms |
3312 KB |
Output is correct |
| 7 |
Correct |
201 ms |
4128 KB |
Output is correct |
| 8 |
Correct |
301 ms |
5236 KB |
Output is correct |
| 9 |
Correct |
468 ms |
7600 KB |
Output is correct |
| 10 |
Correct |
588 ms |
10348 KB |
Output is correct |
| 11 |
Correct |
1326 ms |
21820 KB |
Output is correct |
| 12 |
Correct |
1521 ms |
23356 KB |
Output is correct |
| 13 |
Correct |
1527 ms |
24324 KB |
Output is correct |
| 14 |
Correct |
1808 ms |
25360 KB |
Output is correct |
| 15 |
Correct |
1597 ms |
26632 KB |
Output is correct |
