#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 2e4+5;
const int maxt = 55;
ll pts[maxn];
int foo[maxt][maxn];
int n, t, s;
struct segtree
{
ll st[4*maxn], lz[4*maxn];
void push(int p, int L, int R)
{
if(!lz[p]) return;
st[p] += lz[p];
if(L != R)
{
lz[2*p] += lz[p];
lz[2*p+1] += lz[p];
}
lz[p] = 0;
}
void update(int i, int j, int dx, int p = 1, int L = 0, int R = t)
{
push(p, L, R);
if(i> R || j< L) return;
if(i<= L && R<= j)
{
lz[p] += dx;
push(p, L, R);
return;
}
int M = (L+R)/2;
update(i, j, dx, p<<1, L, M);
update(i, j, dx, p<<1|1, M+1, R);
st[p] = min(st[p<<1], st[p<<1|1]);
}
ll ask(int i, int j, int p = 1, int L = 0, int R = t)
{
if(i> R || j< L) return 1e9;
push(p, L, R);
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
ll x = ask(i, j, p<<1, L, M);
ll y = ask(i, j, p<<1|1, M+1, R);
return min(x, y);
}
};
segtree ez[maxt];
ii rang[maxt];
ll dp[maxt][maxn];
int main()
{
scanf("%d %d %d", &n, &t, &s);
for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
for(int i = 1; i<= n; i++)
{
char bar[maxn]; scanf("%s", bar+1);
for(int j = 1; j<= t; j++) foo[i][j] = bar[j]-'0';
}
for(int i = 1; i<= n; i++) rang[i] = {-1, -1};
ez[0].update(1, t, 1e9);
for(int i = 1; i<= s; i++) ez[i].update(0, 0, 1e9);
// printf("%lld\n", ez[1].ask(0, 0));
for(int i = 1; i<= t; i++)
{
// printf("i = %d\n", i);
for(int j = 1; j<= n; j++)
{
if(foo[j][i])
{
if(rang[j].X == -1)
{
rang[j] = {i, i};
}
else rang[j].Y = i;
// printf("update [%d..%d] +%lld\n", rang[j].X-1, i-1, pts[i]);
for(int k = 0; k<= s; k++) ez[k].update(rang[j].X-1, i-1, pts[i]);
}
else
{
if(rang[j].X == -1) continue;
else
{
for(int k = rang[j].X; k<= rang[j].Y; k++)
{
// printf("[%d..%d] -%lld\n", rang[j].X-1, k-1, pts[k]);
for(int k2 = 0; k2<= s; k2++) ez[k2].update(rang[j].X-1, k-1, -pts[k]);
}
rang[j] = {-1, -1};
}
}
}
for(int rem = 1; rem<= s; rem++)
{
dp[rem][i] = ez[rem-1].ask(0, i-1);
// printf("kuydp[%d][%d] = %lld\n", rem, i, dp[rem][i]);
ez[rem].update(i, i, dp[rem][i]);
// printf("k\n");
}
}
for(int i = 1; i<= s; i++) printf("%lld\n", dp[i][t]);
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:68: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:69:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i<= t; i++) scanf("%lld", &pts[i]);
~~~~~^~~~~~~~~~~~~~~~~
popeala.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char bar[maxn]; scanf("%s", bar+1);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
2552 KB |
Output is correct |
| 2 |
Correct |
398 ms |
2476 KB |
Output is correct |
| 3 |
Correct |
410 ms |
2584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
9036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
760 KB |
Output is correct |
| 3 |
Correct |
402 ms |
2552 KB |
Output is correct |
| 4 |
Correct |
398 ms |
2476 KB |
Output is correct |
| 5 |
Correct |
410 ms |
2584 KB |
Output is correct |
| 6 |
Execution timed out |
2048 ms |
9036 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
