Submission #741433

#	Time	Username	Problem	Language	Result	Execution time	Memory
741433		abcvuitunggio	Popeala (CEOI16_popeala)	C++17	100 / 100	275 ms	18764 KiB

popeala

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int INF=1e18;
int dp[20001][51],n,T,s,t[20001],last[20001][51],a[51];
string score[51];
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> T >> s;
    for (int i=1;i<=T;i++){
        cin >> t[i];
        t[i]+=t[i-1];
    }
    for (int i=0;i<n;i++)
        cin >> score[i];
    for (int i=1;i<=T;i++){
        last[i][n]=i;
        for (int j=0;j<n;j++)
            last[i][j]=(score[j][i-1]=='0'?i:last[i-1][j]);
    }
    for (int i=1;i<=T;i++)
        sort(last[i],last[i]+n+1);
    for (int i=1;i<=T;i++)
        dp[i][0]=INF;
    for (int i=1;i<=s;i++){
        for (int j=0;j<=n;j++)
            a[j]=INF;
        dp[0][i]=INF;
        for (int j=1;j<=T;j++){
            dp[j][i]=INF;
            for (int k=0;k<=n;k++){
                for (int l=last[j-1][k]+1;l<=last[j][k];l++)
                    a[k]=min(a[k],dp[l-1][i-1]-t[l-1]*k);
                dp[j][i]=min(dp[j][i],a[k]+t[j]*k);
            }
        }
        cout << dp[T][i] << '\n';
    }
}

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