oj.uz

Submission #483771

# Submission time Handle Problem Language Result Execution time Memory
483771 2021-11-01T04:41:41 Z phamhoanghiep Popeala (CEOI16_popeala) C++17
100 / 100
 276 ms 18244 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8908 KB Output is correct
2 Correct 4 ms 9164 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9464 KB Output is correct
2 Correct 10 ms 9540 KB Output is correct
3 Correct 11 ms 9560 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10316 KB Output is correct
2 Correct 45 ms 10712 KB Output is correct
3 Correct 57 ms 11084 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8908 KB Output is correct
2 Correct 4 ms 9164 KB Output is correct
3 Correct 11 ms 9464 KB Output is correct
4 Correct 10 ms 9540 KB Output is correct
5 Correct 11 ms 9560 KB Output is correct
6 Correct 32 ms 10316 KB Output is correct
7 Correct 45 ms 10712 KB Output is correct
8 Correct 57 ms 11084 KB Output is correct
9 Correct 89 ms 12356 KB Output is correct
10 Correct 118 ms 13308 KB Output is correct
11 Correct 262 ms 17984 KB Output is correct
12 Correct 276 ms 18244 KB Output is correct
13 Correct 265 ms 18196 KB Output is correct
14 Correct 271 ms 18136 KB Output is correct
15 Correct 272 ms 18244 KB Output is correct