#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int K=52;
const int N=20050;
const ll inf=1e18;
int n,t,s;
ll dp[2][N],sum[K][N],pts[N];
char res[K][N];
int go[K][N];
ll Get(int l, int r)
{
ll s=pts[r]-pts[l-1],cnt=0;
for(int i=1;i<=n;i++)
{
if(sum[i][r]-sum[i][l-1]==r-l+1) cnt++;
}
return s*cnt;
}
const int M=2*N;
int root,tsz,ls[M],rs[M];
ll mn[M],lzy[M];
void Build(int &c, int ss, int se, int x)
{
c=++tsz;lzy[c]=0;
if(ss==se){ mn[c]=dp[x][ss-1];return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid,x);
Build(rs[c],mid+1,se,x);
mn[c]=min(mn[ls[c]],mn[rs[c]]);
}
void Add(int c, int ss, int se, int qs, int qe, ll x)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ mn[c]+=x;lzy[c]+=x;return;}
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,x);
Add(rs[c],mid+1,se,qs,qe,x);
mn[c]=min(mn[ls[c]],mn[rs[c]])+lzy[c];
}
ll Get(int c, int ss, int se, int qs, int qe)
{
if(qs>qe || qs>se || ss>qe) return inf;
if(qs<=ss && qe>=se) return mn[c];
int mid=ss+se>>1;
return min(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe))+lzy[c];
}
void Solve(int x)
{
Build(root,1,t,x^1);
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
if(res[j][i]=='1') Add(root,1,t,go[j][i],i,pts[i]);
else for(int k=i-1;res[j][k]=='1';k--) Add(root,1,t,go[j][k],k,-pts[k]);
}
dp[x][i]=Get(root,1,t,1,i);
}
for(int i=1;i<=tsz;i++) ls[i]=rs[i]=0;
tsz=root=0;
}
int main()
{
scanf("%i %i %i",&n,&t,&s);
for(int i=1;i<=t;i++) scanf("%lld",&pts[i]);
for(int i=1;i<=n;i++)
{
scanf("%s",res[i]+1);
for(int j=1;j<=t;j++)
{
sum[i][j]=sum[i][j-1]+(res[i][j]=='1');
if(res[i][j]=='1')
{
if(res[i][j-1]=='1') go[i][j]=go[i][j-1];
else go[i][j]=j;
}
}
}
for(int i=0;i<2;i++) for(int j=0;j<=t;j++) dp[i][j]=inf;
dp[0][0]=0;
for(int i=1;i<=s;i++)
{
for(int j=0;j<=t;j++) dp[i&1][j]=inf;
Solve(i&1);
printf("%lld\n",dp[i&1][t]);
}
return 0;
}
Compilation message
popeala.cpp: In function 'void Build(int&, int, int, int)':
popeala.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
popeala.cpp: In function 'void Add(int, int, int, int, int, long long int)':
popeala.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
popeala.cpp: In function 'long long int Get(int, int, int, int, int)':
popeala.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
popeala.cpp: In function 'int main()':
popeala.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&n,&t,&s);
~~~~~^~~~~~~~~~~~~~~~~~~~~
popeala.cpp:66:29: 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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",res[i]+1);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
1400 KB |
Output is correct |
| 2 |
Correct |
313 ms |
1332 KB |
Output is correct |
| 3 |
Correct |
337 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1638 ms |
2556 KB |
Output is correct |
| 2 |
Execution timed out |
2051 ms |
3064 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
888 KB |
Output is correct |
| 3 |
Correct |
330 ms |
1400 KB |
Output is correct |
| 4 |
Correct |
313 ms |
1332 KB |
Output is correct |
| 5 |
Correct |
337 ms |
1272 KB |
Output is correct |
| 6 |
Correct |
1638 ms |
2556 KB |
Output is correct |
| 7 |
Execution timed out |
2051 ms |
3064 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
