#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sf scanf
#define pf printf
#define INF 1023456789
typedef pair<int,int> ii;
int t,n,s,p[20005],r[55][20005],pfx[200005];
ii pv[20005][55];
int dp[55][20005],st[55][20][20005];
char ch;
int main(){
sf("%d%d%d",&n,&t,&s);
for(int i=1;i<=t;++i){
sf("%d",&p[i]);
pfx[i]=p[i]+pfx[i-1];
}
for(int i=0;i<n;++i){
for(int j=1;j<=t;++j){
sf(" %c",&ch);
r[i][j]=ch-'0'+r[i][j-1];
}
}
for(int i=1;i<=t;++i){
for(int j=0;j<=n;++j){
//find range with exactly j all 1s
int lo=1,hi=i,mid,res=-1,res2=-1;
while(lo<=hi){
mid=(lo+hi)/2;
int cnt=0;
for(int k=0;k<n;++k){
if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt;
}
if(cnt>=j)res=mid,hi=mid-1;
else lo=mid+1;
}
lo=1,hi=i;
while(lo<=hi){
mid=(lo+hi)/2;
int cnt=0;
for(int k=0;k<n;++k){
if(r[k][i]-r[k][mid-1]==i-mid+1)++cnt;
}
if(cnt<=j)res2=mid,lo=mid+1;
else hi=mid-1;
}
pv[i][j]={res,res2};
}
}
for(int i=1;i<=t;++i)dp[0][i]=INF;
for(int i=1;i<=s;++i)dp[i][0]=INF;
for(int k=1;k<=s;++k){
for(int j=0;j<=n;++j){//how many all 1s
for(int i=1;i<=t;++i){//position
st[j][0][i]=dp[k-1][i-1]-pfx[i-1]*j;
}
for(int k=1;k<15;++k){
for(int i=1;i+(1<<k)<=t+1;++i){
st[j][k][i]=min(st[j][k-1][i],st[j][k-1][i+(1<<(k-1))]);
}
}
}
for(int i=1;i<=t;++i){
dp[k][i]=INF;
for(int j=0;j<=n;++j){//how many all 1s
int x=pv[i][j].fi,y=pv[i][j].se;
if(x==-1||y==-1)continue;
int l=32-__builtin_clz(y-x+1)-1;
dp[k][i]=min(dp[k][i],j*pfx[i]+min(st[j][l][x],st[j][l][y-(1<<l)+1]));
}
}
}
for(int i=1;i<=s;++i)pf("%d\n",dp[i][t]);
}
/*
2 3 3
4 3 5
101
110
*/
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:17:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | sf("%d%d%d",&n,&t,&s);
| ^
popeala.cpp:19:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | sf("%d",&p[i]);
| ^
popeala.cpp:24:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | sf(" %c",&ch);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
3928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
231 ms |
9264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
