#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
/*
Can we use dp[T] (1-dimensional) for each S-layer, and sweep for N?
*/
template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return a>b?a=b,1:0;}
int rpl(int& a, int b){return !~a||b<a?a=b,1:0;}
const int MT=1<<15;
const int MN=52, MS=52;
const int INF=2e9+10;
int T, N, S, a[MT], p[MT], pr[MN][MT], dp[2][MT], o[MN];
bool b[MN][MT];
char s[MN];
struct val{public: int i, v;};
struct dque : public std::deque<val>
{
public:
int k, r;
bool chk(int nl, int nr)
{
for(;r <= nr;++r)
{
if(!~dp[0][r])
continue;
val x = {r, dp[0][r]-p[r]*k};
for(;!empty() && x.v <= back().v;)
pop_back();
push_back(x);
}
for(;!empty() && front().i <= nl;)
pop_front();
return !empty();
}
int get() {return front().v;}
} q[MN];
int main(void)
{
scanf("%d%d%d", &N, &T, &S);
for(int i=0;i<T;++i)
scanf("%d", a+i), p[i+1]=p[i]+a[i];
for(int i=0;i<N;++i)
{
scanf(" %s", s);
pr[i][0] = -1;
for(int j=0;j<T;++j)
{
b[i][s[j]]=s[j]=='0';
pr[i][j+1] = s[j]=='0'?j:pr[i][j];//prev occurence in [0, j)
}
}
for(int i=0;i<=N;++i)
q[i].k=i;
memset(dp, -1, sizeof dp);
dp[0][0] = 0;
o[0]=-1;
for(int i=1;i<=S;++i)
{
for(int j=1;j<=T;++j)
{
for(int k=0;k<N;++k)
o[k+1]=pr[k][j];
std::sort(o+1, o+N+1);
o[N+1]=j-1;// CHECK (J-1) IS CORRECT?
for(int k=0;k<=N;++k)
{
//printf("\tRANGE (%d): (%d, %d]\n", k, o[k], o[k+1]);
if(q[k].chk(o[k], o[k+1]))
rpl(dp[1][j], q[k].get() + k*p[j]);//(]
}
//printf("dp[%d][%d] = %d\n", i, j, dp[1][j]);
}
printf("%d\n", dp[1][T]);
memcpy(dp[0], dp[1], sizeof dp[1]);
memset(dp[1], -1, sizeof dp[1]);
for(int j=0;j<=N;++j)
q[j].clear(), q[j].r=0;
}
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:57:13: warning: array subscript has type 'char' [-Wchar-subscripts]
b[i][s[j]]=s[j]=='0';
^
popeala.cpp:48:7: 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:50:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a+i), p[i+1]=p[i]+a[i];
~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
popeala.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %s", s);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
60 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
250 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
359 ms |
1792 KB |
Output is correct |
| 3 |
Correct |
427 ms |
2136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
5 ms |
896 KB |
Output is correct |
| 3 |
Correct |
63 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
54 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
60 ms |
1280 KB |
Output is correct |
| 6 |
Correct |
250 ms |
1912 KB |
Output is correct |
| 7 |
Correct |
359 ms |
1792 KB |
Output is correct |
| 8 |
Correct |
427 ms |
2136 KB |
Output is correct |
| 9 |
Correct |
536 ms |
2936 KB |
Output is correct |
| 10 |
Correct |
895 ms |
3444 KB |
Output is correct |
| 11 |
Correct |
1399 ms |
6136 KB |
Output is correct |
| 12 |
Correct |
1472 ms |
6352 KB |
Output is correct |
| 13 |
Execution timed out |
2100 ms |
6392 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
