#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();
for (int i=1; i<=T; i++) {
freq[i] = ST.Num(i,i);
dp[i][1] = Sum[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]);
}
}
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]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
226 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
