Submission #682955

#TimeUsernameProblemLanguageResultExecution timeMemory
682955Rafi22Popeala (CEOI16_popeala)C++14
0 / 100
2081 ms1276 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long #define ld long double ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; const int N=20007,M=57; int DP[N][M]; char is[M][N]; int a[N]; bool act[M]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m,n,s; cin>>m>>n>>s; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) a[i]+=a[i-1]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>is[i][j]; for(int i=1;i<=s;i++) DP[0][i]=infl; for(int i=1;i<=n;i++) { DP[i][0]=infl; for(int j=1;j<=s;j++) { int c=0; for(int l=1;l<=m;l++) { if(is[l][i]=='1') { act[l]=1; c++; } else act[l]=0; } DP[i][j]=infl; for(int l=i-1;l>=0;l--) { DP[i][j]=min(DP[i][j],DP[l][j-1]+(a[i]-a[l])*c); for(int k=1;k<=m;k++) { if(act[k]&&is[k][l]=='0') { act[k]=0; c--; } } } } } for(int i=1;i<=n;i++) cout<<DP[n][i]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...