Submission #698082

#	Time	Username	Problem	Language	Result	Execution time	Memory
698082		abcvuitunggio	Popeala (CEOI16_popeala)	C++17	0 / 100	11 ms	2396 KiB

popeala

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
const int INF=1e18;
int dp[20001][51],n,T,s,t[20001],a[51][20001],cur;
string score[51];
vector <pair <int, int>> ve[51];
int C(int i, int j){
    int cnt=0;
    for (int k=1;k<=n;k++)
        cnt+=(a[k][j]-a[k][i-1]==j-i+1);
    return (t[j]-t[i-1])*cnt;
}
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=1;i<=n;i++){
        cin >> score[i];
        for (int j=0;j<T;j++)
            a[i][j+1]=a[i][j]+score[i][j]-'0';
    }
    for (int i=1;i<=T;i++)
        dp[i][0]=INF;
    ve[0].push_back({1,0});
    for (int j=1;j<=s;j++){
        for (int i=j;i<=T;i++){
            int k=upper_bound(ve[j-1].begin(),ve[j-1].end(),make_pair(i,INF))-ve[j-1].begin()-1;
            k=ve[j-1][k].second;
            dp[i][j]=dp[k][j-1]+C(k+1,i);
            while (!ve[j].empty()){
                auto [x,k]=ve[j].back();
                if (x>i&&dp[i][j]+C(i+1,x)<dp[k][j]+C(k+1,x)){
                    ve[j].pop_back();
                    continue;
                }
                break;
            }
            if (ve[j].empty())
                ve[j].push_back({1,i});
            else{
                auto [x,k]=ve[j].back();
                int l=x+1,r=n,kq=-1;
                while (l<=r){
                    int mid=(l+r)>>1;
                    if (mid>i&&dp[i][j]+C(i+1,mid)<dp[k][j]+C(k+1,mid)){
                        kq=mid;
                        r=mid-1;
                    }
                    else
                        l=mid+1;
                }
                if (kq!=-1)
                    ve[j].push_back({kq,i});
            }
        }
        cout << dp[T][j] << '\n';
    }
}

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