제출 #1212600

#제출 시각아이디문제언어결과실행 시간메모리
1212600MMihalevPopeala (CEOI16_popeala)C++20
100 / 100
481 ms32236 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int MAX_N=5e1+5; const int MAX_T=2e4+4; const int INF=2e9+69; int n,t,s; int points[MAX_T]; bool test[MAX_N][MAX_T]; vector<pair<int,int>>intervals[MAX_T]; vector<pair<int,int>>leftends[MAX_T]; int sum[MAX_T]; int dp[MAX_T][MAX_N]; void precompute() { for(int guy=1;guy<=n;guy++) { int cons=0; for(int i=1;i<=t;i++) { if(test[guy][i]==1)cons++; else cons=0; if(cons) { sum[i]++; leftends[i].push_back({cons,guy}); } } } for(int i=1;i<=t;i++) { if(leftends[i].size()==0)continue; sort(leftends[i].begin(),leftends[i].end()); int last=leftends[i][0].first; int cur_sum=1; for(int j=1;j<leftends[i].size();j++) { if(last==leftends[i][j].first) { cur_sum++; } else { intervals[i].push_back({i-last,sum[i]}); sum[i]-=cur_sum; cur_sum=1; last=leftends[i][j].first; } } intervals[i].push_back({i-last,sum[i]}); } } int p[MAX_T][MAX_N]; void solve() { for(int i=0;i<=t;i++) { for(int k=0;k<=s;k++) { dp[i][k]=INF; } } dp[0][0]=0; int k,x,i; for(k=1;k<=s;++k) { for(x=0;x<=n;++x) { p[0][x]=dp[0][k-1]-x*points[0]; for(i=1;i<=t;++i) { p[i][x]=min(dp[i][k-1]-x*points[i],p[i-1][x]); } } for(i=1;i<=t;++i) { int zero=i,prevlast=i; for(auto&[last,cost]:intervals[i]) { zero=last; dp[i][k]=min(dp[i][k],p[prevlast-1][cost]+cost*points[i]); prevlast=last; } if(zero>0)dp[i][k]=min(dp[i][k],p[zero-1][0]); } } for(int k=1;k<=s;k++) { cout<<dp[t][k]<<"\n"; } } int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #ifdef ONLINE_JUDGE freopen("popeala.in", "r", stdin); freopen("popeala.out", "w", stdout); #endif cin>>n>>t>>s; for(int i=1;i<=t;i++) { cin>>points[i]; points[i]+=points[i-1]; } for(int i=1;i<=n;i++) { string s; cin>>s; for(int j=0;j<t;j++) { if(s[j]=='0')test[i][j+1]=0; else test[i][j+1]=1; } } precompute(); solve(); 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...