Submission #612609

#TimeUsernameProblemLanguageResultExecution timeMemory
612609CSQ31Popeala (CEOI16_popeala)C++17
100 / 100
406 ms14344 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...