oj.uz

Submission #128006

# Submission time Handle Problem Language Result Execution time Memory
128006 2019-07-10T10:21:35 Z Plurm Popeala (CEOI16_popeala) C++11
100 / 100
 1513 ms 18424 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))];
        }
    }
}
inline 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 5 ms 4088 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4984 KB Output is correct
2 Correct 37 ms 4984 KB Output is correct
3 Correct 38 ms 4860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 5988 KB Output is correct
2 Correct 224 ms 6620 KB Output is correct
3 Correct 289 ms 7200 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4088 KB Output is correct
2 Correct 6 ms 4344 KB Output is correct
3 Correct 40 ms 4984 KB Output is correct
4 Correct 37 ms 4984 KB Output is correct
5 Correct 38 ms 4860 KB Output is correct
6 Correct 155 ms 5988 KB Output is correct
7 Correct 224 ms 6620 KB Output is correct
8 Correct 289 ms 7200 KB Output is correct
9 Correct 441 ms 8888 KB Output is correct
10 Correct 657 ms 10232 KB Output is correct
11 Correct 1396 ms 17000 KB Output is correct
12 Correct 1474 ms 17272 KB Output is correct
13 Correct 1467 ms 18424 KB Output is correct
14 Correct 1513 ms 18372 KB Output is correct
15 Correct 1479 ms 18344 KB Output is correct