Submission #536505

#	Time	Username	Problem	Language	Result	Execution time	Memory
536505		tqbfjotld	Popeala (CEOI16_popeala)	C++14	100 / 100	1259 ms	13316 KiB

popeala

#include <bits/stdc++.h>
using namespace std;

int T,N,S;

int dp[40005][55];
int pre[40005];
deque<pair<int,int> > slide[55];
int curl[55];
int curr[55];
const int INF = 2000000001;

int loc[400005][55];

long long spt[400005][20];
void sp_init(){
    for (int x = 1; x<20; x++){
        for (int y = 0; y<T-(1<<(x-1)); y++){
            spt[y][x] = spt[y][x-1]&spt[y+(1<<(x-1))][x-1];
        }
    }
}

long long sp_qu(int a, int b){
    int len = b-a+1;
    int t2 = 31-__builtin_clz(len);
    long long res = (spt[a][t2])&(spt[b-(1<<t2)+1][t2]);
    //printf("%d to %d res %lld\n",a,b,res);
    return res;
}

void window(int X, int l, int r, int k){
    if (r<l && curr[X]<curl[X]) return;
    //printf("k=%d, slide %d %d to %d %d, %d\n",k,curl[X],curr[X],l,r,X);
    for (int x = curr[X]+1; x<=r; x++){
        if (x<k-1) continue;
        int val = dp[x][k]-(N-X+1)*pre[x];
        //printf("push %d (%d) into %d\n",val,dp[x][k],X);
        while ((!slide[X].empty()) && slide[X].back().first>=val){
            slide[X].pop_back();
        }
        slide[X].push_back({val,x});
    }
    while ((!slide[X].empty()) && slide[X][0].second<l){
        slide[X].pop_front();
    }
    curl[X] = l;
    curr[X] = r;
}


int main(){
    scanf("%d%d%d",&N,&T,&S);
    for (int x = 0; x<T; x++){
        scanf("%d",&pre[x]);
        if (x!=0) pre[x] += pre[x-1];
    }
    for (int x = 0; x<N; x++){
        for (int y = 0; y<T; y++){
            char c;
            scanf(" %c",&c);
            if (c=='1'){
                spt[y][0] += (1LL<<x);
            }
        }
    }
    sp_init();

    for (int x = 0; x<T; x++){
        for (int y = 1; y<=N+1; y++){
            int l = -1;
            int r = x+1;
            while (l+1<r){
                int mid = (l+r)/2;
                long long res = sp_qu(mid,x);
                if ((int)__builtin_popcountll(res)>N-y){
                    r = mid;
                }
                else{
                    l = mid;
                }
            }
            loc[x][y] = l;
            //printf("loc %d %d = %d\n",x,y,l);
        }
        loc[x][0] = x;
    }

    for (int k = 1; k<=S; k++){
        for (int x = 0; x<T; x++){
            dp[x][k] = INF;
        }
    }

    for (int k = 1; k<=S; k++){
        for (int x = 0; x<=N+1; x++){
            slide[x].clear();
            curr[x] = -2;
            curl[x] = -1;
        }
        for (int x = 0; x<T; x++){
            if (x<k-1) continue;
            if (k==1){
                dp[x][k] = __builtin_popcountll(sp_qu(0,x))*pre[x];
                //printf("dp %d %d = %d\n",x,k,dp[x][k]);
                continue;
            }
            int ans = INF;
            for (int y = 1; y<=N+1; y++){
                window(y,min(x,loc[x][y]),min(x-1,loc[x][y-1]-1),k-1);
                if (slide[y].empty()) continue;
                ans = min(ans,slide[y][0].first+(N-y+1)*pre[x]);
            }
            dp[x][k] = ans;
            //printf("dp %d %d = %d\n",x,k,dp[x][k]);
        }
        printf("%d\n",dp[T-1][k]);
    }
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d%d%d",&N,&T,&S);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d",&pre[x]);
      |         ~~~~~^~~~~~~~~~~~~~
popeala.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |             scanf(" %c",&c);
      |             ~~~~~^~~~~~~~~~

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