oj.uz

Submission #536505

# Submission time Handle Problem Language Result Execution time Memory
536505 2022-03-13T12:56:16 Z tqbfjotld Popeala (CEOI16_popeala) C++14
100 / 100
 1259 ms 13316 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 672 KB Output is correct
2 Correct 36 ms 672 KB Output is correct
3 Correct 33 ms 596 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 1768 KB Output is correct
2 Correct 220 ms 2288 KB Output is correct
3 Correct 261 ms 2816 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 44 ms 672 KB Output is correct
4 Correct 36 ms 672 KB Output is correct
5 Correct 33 ms 596 KB Output is correct
6 Correct 161 ms 1768 KB Output is correct
7 Correct 220 ms 2288 KB Output is correct
8 Correct 261 ms 2816 KB Output is correct
9 Correct 381 ms 4548 KB Output is correct
10 Correct 574 ms 5852 KB Output is correct
11 Correct 1107 ms 13216 KB Output is correct
12 Correct 1175 ms 13268 KB Output is correct
13 Correct 1189 ms 13256 KB Output is correct
14 Correct 1222 ms 13316 KB Output is correct
15 Correct 1259 ms 13296 KB Output is correct