Submission #483771

#	Time	Username	Problem	Language	Result	Execution time	Memory
483771		phamhoanghiep	Popeala (CEOI16_popeala)	C++17	100 / 100	276 ms	18244 KiB

popeala

#include<bits/stdc++.h>
using namespace std;
const int maxt=2e4+2;
const int maxn=55;
const int inf=2e9+2;
int n,t,s;
int a[maxt];
int pf[maxt];
char c[maxn][maxt];
int prv[maxn][maxt]; // last '0'
int dp[maxt][maxn];
int best[maxt][maxn];
int last[maxt][maxn]; // store 'prv's for each questions of contestants.
signed main() {
    cin>>n>>t>>s;
    for(int i=1 ; i<=t ; i++) {
        cin>>a[i];
        pf[i]=pf[i-1]+a[i];
    }
    for(int i=1 ; i<=n ; i++) {
        cin>>c[i]+1;
        for(int j=1 ; j<=t ; j++) {
            if(c[i][j]=='0') prv[i][j]=j;
            else prv[i][j]=prv[i][j-1];
            ////cout<<"prev "<<i<<" "<<j<<" = "<<prv[i][j]<<endl;
        }
    }
    for(int i=0 ; i<maxt ; i++) {
        for(int j=0 ; j<maxn ; j++) {
            dp[i][j]=best[i][j]=inf;
        }
    }
    dp[0][0]=0;
    for(int i=1 ; i<=t ; i++) {
        for(int j=1 ; j<=n ; j++) {
            last[i][j]=prv[j][i];
        }
        last[i][n+1]=i;
        sort(last[i]+1,last[i]+2+n);
        for(int j=1 ; j<=n+1 ; j++) {
            //cout<<"last "<<i<<" "<<j<<" = "<<last[i][j]<<endl;
        }
    }
    for(int sub=1 ; sub<=s ; sub++) {
        for(int i=1 ; i<=t ; i++) {
            for(int j=0 ; j<=n ; j++) {
                best[i][j]=min(best[i-1][j],dp[i-1][sub-1]-pf[i-1]*j);
                //cout<<"best "<<i<<" "<<j<<" = "<<best[i][j]<<endl;
            }
        }
        for(int i=1 ; i<=t ; i++) {
            for(int j=1 ; j<=n+1 ; j++) {
                //cout<<"best "<<last[i][j]<<" "<<j-1<<" = "<<best[last[i][j]][j-1]<<endl;
                int x=pf[i]*(j-1)+best[last[i][j]][j-1];
                //cout<<"x = "<<x<<endl;
                if(j<=n) dp[i][sub]=min(dp[i][sub],x);
                else if(last[i][j-1]!=i) dp[i][sub]=min(dp[i][sub],x);
                ////cout<<"dp "<<i<<" "<<sub<<" = "<<x<<endl;
            }
            //cout<<"dp "<<i<<" "<<sub<<" = "<<dp[i][sub]<<endl;
        }
        cout<<dp[t][sub]<<'\n';
    }
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:21:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         cin>>c[i]+1;
      |              ~~~~^~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74