#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define lll __int128
#define ull unsigned long long
#define fi first
#define se second
#define db double
#define ld long double
#define lld __float128
/// order_of_key, find_by_order
template<class T, class COMP>
using custom_set = tree<T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());
const int MAXT = 20005;
bool slv[55][MAXT];
ll tr[MAXT*4], psh[MAXT*4], dp[MAXT][55], val[MAXT];
int ls[55];
void push(int v, int l, int r)
{
if(!psh[v])
return;
tr[v] += psh[v];
if(l != r)
{
psh[v*2] += psh[v];
psh[v*2+1] += psh[v];
}
psh[v] = 0;
}
void Add(int l, int r, int L, int R, int v, ll x)
{
if(l >= L && r <= R)
{
psh[v] += x;
push(v, l, r);
return;
}
push(v, l, r);
if(l > R || r < L)
return;
int m = (l+r) / 2;
Add(l, m, L, R, v*2, x);
Add(m+1, r, L, R, v*2+1, x);
tr[v] = min(tr[v*2], tr[v*2+1]);
}
ll Min(int l, int r, int L, int R, int v)
{
if(l >= L && r <= R)
{
push(v, l, r);
return tr[v];
}
if(l > R || r < L)
return 1e18;
push(v, l, r);
int m = (l+r) / 2;
return min(Min(l, m, L, R, v*2), Min(m+1, r, L, R, v*2+1));
}
void Build(int l, int r, int v)
{
if(l == r)
{
tr[v] = 0;
psh[v] = 0;
return;
}
int m = (l+r) / 2;
Build(l, m, v*2);
Build(m+1, r, v*2+1);
tr[v] = psh[v] = 0;
}
int main()
{
int n, t, s; cin >> n >> t >> s;
for(int i = 0; i < t; i++)
{
cin >> val[i];
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < t; j++)
{
char ch; cin >> ch;
slv[i][j] = (ch == '1');
}
}
for(int i = 1; i <= t; i++)
{
dp[0][i] = 1e18;
}
for(int j = 1; j <= s; j++)
{
for(int i = 0; i < n; i++)
{
ls[i] = 0;
}
Build(0, n, 1);
dp[j][0] = 1e18;
for(int i = 0; i < t; i++)
{
Add(0, n, i, i, 1, dp[j-1][i]);
for(int x = 0; x < n; x++)
{
if(slv[x][i])
{
Add(0, n, ls[x], i, 1, val[i]);
}
else
{
ll sm = 0;
for(int ps = i-1; ps >= ls[x]; ps--)
{
sm += val[ps];
Add(0, n, ps, ps, 1, -sm);
}
ls[x] = i+1;
}
}
dp[j][i+1] = Min(0, n, 0, i, 1);
}
// for(int i = 0; i <= t; i++)
// {
// cout << dp[j][i] << ' ';
// } cout << '\n';
cout << dp[j][t] << '\n';
}
}
/// shche ne vmerla Ykraina
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
