oj.uz

Submission #128004

# Submission time Handle Problem Language Result Execution time Memory
128004 2019-07-10T10:20:15 Z Plurm Popeala (CEOI16_popeala) C++11
26 / 100
 2000 ms 18204 KB 
#include <bits/stdc++.h>
#define call(x) (1ll*dp[i-1][(x)-1] - 1ll*k*qs[(x)-1])
using namespace std;
char res[64][20005];
long long dp[64][20005];
long long cmask[20005];
int qs[20005];
int pts[20005];
long long ST[15][32768];
void build(){
    for(int j = 0; j < 32768; j++){
        ST[0][j] = j < 20005 ? cmask[j] : 0ll;
    }
    for(int i = 1; i < 15; i++){
        for(int j = 0; j + (1 << i) - 1 < 32768; j++){
            ST[i][j] = ST[i-1][j] & ST[i-1][j+(1<<(i-1))];
        }
    }
}
int query(int l, int r){
    int d = r-l+1;
    int k = log2(d);
    return __builtin_popcountll(ST[k][l] & ST[k][r-(1 << k)+1]);
}
int f[64][20005];
int main(){
    int n,t,s;
    scanf("%d%d%d",&n,&t,&s);
    for(int i = 1; i <= t; i++){
        scanf("%d",pts+i);
        qs[i] = qs[i-1] + pts[i];
    }
    for(int i = 0; i < n; i++){
        scanf("%s",res[i]+1);
    }
    for(int i = 1; i <= t; i++){
        long long mask = 0ll;
        for(int j = 0; j < n; j++){
            if(res[j][i] == '1') mask |= 1ll << j;
        }
        cmask[i] = mask;
    }
    build();
    for(int i = 1; i <= t; i++){
        for(int k = 0; k <= n+1; k++){
            int lo = 1;
            int hi = i;
            int mid;
            while(lo < hi){
                mid = (lo + hi)/2;
                if(query(mid, i) >= k){
                    hi = mid;
                }else{
                    lo = mid+1;
                }
            }
            if(query(lo, i) < k) f[k][i] = lo+1;
            else f[k][i] = lo;
        }
    }
    dp[1][0] = 1e18;
    long long initmask = cmask[1];
    for(int j = 1; j <= t; j++){
        initmask &= cmask[j];
        dp[1][j] = __builtin_popcountll(initmask) * qs[j];
    }
    printf("%lld\n",dp[1][t]);
    for(int i = 2; i <= s; i++){
        for(int j = 0; j < i; j++){
            dp[i][j] = 1e18;
        }
        for(int j = i; j <= t; j++){
            dp[i][j] = 2e9;
        }
        for(int k = 0; k <= n; k++){
            deque<int> dq; // Sliding window minimum
            int lastr = 0;
            for(int j = i; j <= t; j++){
                int l = f[k][j];
                int r = f[k+1][j];
                if(query(j,j) < k) continue;
                if(l >= r) continue;
                while(lastr < r){
                    while(!dq.empty() && call(dq.back()) > call(lastr)){
                        dq.pop_back();
                    }
                    dq.push_back(lastr);
                    lastr++;
                }
                while(!dq.empty() && dq.front() < l) dq.pop_front();
                if(!dq.empty())
                    dp[i][j] = min(dp[i][j], call(dq.front()) + 1ll*k*qs[j]);
            }
        }
        printf("%lld\n",dp[i][t]);
    }
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&t,&s);
     ~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",pts+i);
         ~~~~~^~~~~~~~~~~~
popeala.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",res[i]+1);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3960 KB Output is correct
2 Correct 7 ms 4344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 4856 KB Output is correct
2 Correct 51 ms 4984 KB Output is correct
3 Correct 54 ms 4936 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 6008 KB Output is correct
2 Correct 314 ms 6904 KB Output is correct
3 Correct 406 ms 7548 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3960 KB Output is correct
2 Correct 7 ms 4344 KB Output is correct
3 Correct 54 ms 4856 KB Output is correct
4 Correct 51 ms 4984 KB Output is correct
5 Correct 54 ms 4936 KB Output is correct
6 Correct 222 ms 6008 KB Output is correct
7 Correct 314 ms 6904 KB Output is correct
8 Correct 406 ms 7548 KB Output is correct
9 Correct 623 ms 9276 KB Output is correct
10 Correct 916 ms 10772 KB Output is correct
11 Correct 1938 ms 18144 KB Output is correct
12 Execution timed out 2005 ms 18204 KB Time limit exceeded
13 Halted 0 ms 0 KB -