This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+1;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
int a[MAXN],n,m,s;
vector<int>pos[MAXN];
ll dp1[MAXN],dp2[MAXN],pre[51][MAXN];
void tran(){
for(int j=0;j<=m;j++){
for(int i=0;i<=n;i++){
pre[j][i] = dp1[i] - a[i] * j;
if(i)pre[j][i] = min(pre[j][i],pre[j][i-1]);
}
}
for(int i=1;i<=n;i++){
dp2[i] = pre[m][i-1] + m*a[i];
int last = i-1;
for(int j=m-1;j>=0;j--){
last = min(pos[i][j]-1,last);
if(last<0)break;
dp2[i] = min(dp2[i],pre[j][last] + j*a[i]);
}
}
/*
for(int i=0;i<=n;i++)cout<<dp1[i]<<" ";
cout<<'\n';
for(int i=0;i<=n;i++)cout<<dp2[i]<<" ";
cout<<'\n';
* */
cout<<dp2[n]<<'\n';
}
int main(){
owo
cin>>m>>n>>s;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
pos[i].resize(m);
}
for(int i=0;i<m;i++){
int last = 0;
for(int j=1;j<=n;j++){
char c;
cin>>c;
if(c=='0')last = j;
pos[j][i] = last;
}
}
for(int i=1;i<=n;i++)sort(pos[i].begin(),pos[i].end());
for(int i=0;i<=n;i++)dp1[i] = dp2[i] = 1e12;
dp1[0] = 0;
for(int i=1;i<=s;i++){
tran();
//cout<<dp2[n]<<" ";
for(int j=0;j<=n;j++){
dp1[j] = dp2[j];
dp2[j] = 1e12;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |