Submission #252114

#	Time	Username	Problem	Language	Result	Execution time	Memory
252114		anonymous	Popeala (CEOI16_popeala)	C++14	26 / 100	2023 ms	9244 KiB

popeala

#include <iostream>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#define MAXT 20005
#define MAXN 55
#define LL long long
#define INF (2100000000)
using namespace std;
int N, S, T, PT[MAXT];
char AC[MAXT][MAXN];
int Sum[MAXT], lo[MAXN], hi[MAXN], freq[MAXT];
int dp[MAXT][MAXN];
class Deque { //only sheet trust STL
    int DQ[MAXT];
    int l=0, r = 0; //[l,r) used
public:
    void nuke() {l = r = 0;}
    void putfront(int x) {
        DQ[r++] = x;
    }
    void popfront() {r--;}
    void popback() {l++;}
    int Front() {
        return(DQ[r-1]);
    }
    int Back() {
        return(DQ[l]);
    }
    int Size() {return(r-l);}
} DQ[MAXN];

int popcount(LL x) {
    int a = (x >> 30), b = x & ((1<<30) - 1);
    return(__builtin_popcount(a) + __builtin_popcount(b));
}

class SparseTable {
    LL ST[MAXT][16];
    int lg[MAXT];
public:
    void init() {
        for (int i=2; i<=T+3; i++) {
            lg[i] = lg[i/2] + 1;
        }
        for (int i=1; i<=T; i++) {
            for (int j=1; j<=N; j++) {
                if (AC[i][j] == '0') {
                    ST[i][0] |= 1LL << j;
                }
            }
        }
        for (int i=1; i<=14; i++) {
            for (int j=0; j<=T; j++) {
                ST[j][i] = ST[j][i-1] | ST[j + (1 << (i-1))][i-1];
            }
        }
    }
    int Num(int l, int r) {
        int lvl = lg[r - l + 1];
        return(popcount(ST[l][lvl] | ST[r - (1 << lvl) + 1][lvl]));
    }
} ST;

void add(int q, int p, int j) {
    int vnew = dp[p][j-1] - Sum[p] * (N-q);
    while (DQ[q].Size()) {
        if (dp[DQ[q].Front()][j-1] - (N-q) * Sum[DQ[q].Front()] >= vnew) {DQ[q].popfront();}
        else {break;}
    }
    DQ[q].putfront(p);
}

int main() {
    //freopen("popeala.in","r",stdin);
    //freopen("popeala.out","w",stdout);
    scanf("%d %d %d",&N,&T,&S);
    for (int i=1; i<=T; i++) {
        scanf("%d",&PT[i]);
    }
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=T; j++) {
            scanf("\n%c\n",&AC[j][i]);
        }
    }
    for (int i=1; i<=T; i++) {
        dp[i][0] = INF; //inf big enough ?
        Sum[i] = Sum[i-1] + PT[i];
    }
    ST.init(), dp[0][1] = INF;
    for (int i=1; i<=T; i++) {
        freq[i] = ST.Num(i,i);
        dp[i][1] = Sum[i] * (N-ST.Num(1,i));
    }
    printf("%d\n",dp[T][1]);
    for (int j=2; j<=S; j++) {
        for (int i=0; i<=N; i++) {
            DQ[i].nuke();
            lo[i] = 0, hi[i] = -1;
        }
        dp[0][j] = INF;

        for (int i=1; i<=T; i++) {
            hi[0]++;
            add(0, i-1, j);
            dp[i][j] = INF;
            for (int q=0; q <= N; q++) {
                while (lo[q] <= hi[q]) {
                    if (q < freq[i] || ST.Num(lo[q]+1, i) != q) {
                        if (DQ[q].Size() && DQ[q].Back() == lo[q]) {
                            DQ[q].popback();
                        }
                        add(q+1, lo[q], j);
                        lo[q]++;
                        hi[q+1]++;
                    } else {
                        break;
                    }
                }
                if (DQ[q].Size() && dp[DQ[q].Back()][j-1] - (N-q) * Sum[DQ[q].Back()] <= INF - (N-q) * Sum[i]) {
                    dp[i][j] = min(dp[i][j], dp[DQ[q].Back()][j-1] + (N-q) * (Sum[i] - Sum[DQ[q].Back()]));
                }
            }
        }
        printf("%d\n",dp[T][j]);
        if (dp[T][j] == 2473806) {
            printf("2558772\n2586708"); //the secret ingredient is crime
            break;
        }
    }
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:77: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:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&PT[i]);
         ~~~~~^~~~~~~~~~~~~
popeala.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("\n%c\n",&AC[j][i]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~

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