#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 2e9;
int n,m,s;
int a[55][20005];
int sum[20005];
int t[55];
vector<int> p[20005];
ll dp[20005];
int tree[55][60005];
void build(int val, int pos, int l, int r) {
if(l==r) {
tree[val][pos] = -val*sum[l] + dp[l];
return ;
}
int mid = (l+r)/2;
build(val,pos<<1,l,mid); build(val,pos<<1|1,mid+1,r);
tree[val][pos] = min(tree[val][pos<<1], tree[val][pos<<1|1]);
}
int query(int val, int pos, int l, int r, int x, int y) {
if(l>r || r<x || y<l) return inf;
if(x<=l && r<=y) return tree[val][pos];
int mid = (l+r)/2;
return min(query(val,pos<<1,l,mid,x,y), query(val,pos<<1|1,mid+1,r,x,y));
}
int main() {
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++) {
int val;
scanf("%d",&val);
sum[i] = sum[i-1] + val;
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
char tc;
scanf(" %c",&tc);
a[i][j] = tc-'0';
}
}
for(int x=1;x<=m;x++) {
for(int i=1;i<=n;i++) {
if(a[i][x]==0) t[i] = x;
if(t[i]) p[x].push_back(t[i]);
}
p[x].push_back(0);
sort(p[x].rbegin(),p[x].rend());
}
for(int x=1;x<=m;x++) dp[x] = inf;
for(int val=0;val<=n;val++) build(val,1,0,m);
for(int k=1;k<=s;k++) {
for(int x=0;x<=m;x++) dp[x] = inf;
for(int x=1;x<=m;x++) {
int val = n, last = x;
for(auto y : p[x]) {
// printf("\t%d * %d + %d [%d, %d]\n",val,sum[x],query(val,1,0,m,y,last-1),y,last-1);
dp[x] = min(dp[x], (ll)val*sum[x] + query(val,1,0,m,y,x-1));
val--; last = y;
}
// printf("dp %d = %d\n",x,dp[x]);
}
for(int val=0;val<=n;val++) build(val,1,0,m);
printf("%d\n",dp[m]);
}
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:54:17: warning: variable 'last' set but not used [-Wunused-but-set-variable]
int val = n, last = x;
^
popeala.cpp:63:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n",dp[m]);
^
popeala.cpp:28:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&s);
^
popeala.cpp:31:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&val);
^
popeala.cpp:37:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c",&tc);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
1760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1004 ms |
3868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
