oj.uz

답안 #483767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483767 2021-11-01T04:18:39 Z phamhoanghiep 조교 (CEOI16_popeala) C++17
18 / 100
 57 ms 4272 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<=t ; i++) {
        for(int j=0 ; j<=s ; 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++) {
                int x=pf[i]*(j-1)+best[last[i][j]][j-1];
                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[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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 588 KB Output isn't correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1100 KB Output is correct
2 Correct 7 ms 1100 KB Output is correct
3 Correct 8 ms 1100 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2636 KB Output is correct
2 Correct 40 ms 3404 KB Output is correct
3 Correct 57 ms 4272 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 588 KB Output isn't correct