oj.uz

답안 #252098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252098 2020-07-24T06:49:09 Z anonymous 조교 (CEOI16_popeala) C++14
26 / 100
 2000 ms 10500 KB 
#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<=15; 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();
    for (int i=1; i<=T; i++) {
        freq[i] = ST.Num(i,i);
    }
    for (int j=1; 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]);
    }
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 1016 KB Output is correct
2 Correct 47 ms 768 KB Output is correct
3 Correct 49 ms 768 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 1664 KB Output is correct
2 Correct 315 ms 2168 KB Output is correct
3 Correct 404 ms 2552 KB Output is correct

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 54 ms 1016 KB Output is correct
4 Correct 47 ms 768 KB Output is correct
5 Correct 49 ms 768 KB Output is correct
6 Correct 218 ms 1664 KB Output is correct
7 Correct 315 ms 2168 KB Output is correct
8 Correct 404 ms 2552 KB Output is correct
9 Correct 585 ms 3704 KB Output is correct
10 Correct 894 ms 4856 KB Output is correct
11 Correct 1846 ms 10088 KB Output is correct
12 Correct 1967 ms 10008 KB Output is correct
13 Correct 1948 ms 10344 KB Output is correct
14 Execution timed out 2050 ms 10500 KB Time limit exceeded
15 Halted 0 ms 0 KB -