/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=2e4+5;
const ll mod=1e9+7 ;
const ll base=3e18;
/// you will be the best but now you just are trash
/// goal 1/7
ll dp[maxn][53];
char a[53][maxn];
ll pre[53];
ll n;
ll pre1[53][maxn];
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k > o.k; }
// hien tai dang la tim max neu muon tim min thi doi dau cho nay va o cho isect cx doi dau 1 lan nua
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less< > > {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
static const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) return x->p = inf, 0;
if (x->k == y->k)
{
x->p = x->m < y->m ? inf : -inf;
// o cho nay nhe cai x-> m > y->m thanh x->m <y->m
}
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll get(ll x) {
if (empty()) return base;
auto l = *lower_bound(x);
return l.k * x + l.m;
}
} fwt[maxn][53];
void update(ll x,ll p,ll val,ll val1)
{
for (int i=x;i<=n;i+= i&(-i))
{
fwt[i][p].add(val1,val);
}
}
ll get(ll x,ll p,ll sl)
{
ll ans=base;
for (int i=x;i;i-= i&(-i))
{
ans=min(ans,fwt[i][p].get(sl));
}
return ans;
}
ll f[maxn];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("popeala.in", "r"))
{
freopen("popeala.in", "r", stdin);
freopen("popeala.out", "w", stdout);
}
ll m, s;
cin>> m>> n>> s;
for (int i=1;i<=n;i++)
{
ll x;
cin>>x;
f[i]=f[i-1]+x;
}
for (int i=1;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
for (int i=0;i<=n;i++)
{
for (int j=0;j<=s;j++)
{
dp[i][j]=base;
}
}
for (int t=0;t<=s;t++)
{
pre1[t][0]=base;
}
dp[0][0]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=s;j++)
{
ll val=dp[i-1][j];
pre1[j][i]=min(pre1[j][i-1],dp[i-1][j]);
if (val==base) continue;
ll pos=i;
update(pos,j,val,-f[i-1]);
/* if (i<=1&&j==0)
{
cout <<pos<<" "<<val<<" "<<-f[i-1]<<" nch"<<endl;
}*/
}
vector<pll> vt;
ll mx=0;
for (int t=1;t<=m;t++)
{
if (a[t][i]=='1')
{
pre[t]++;
vt.pb(make_pair(pre[t],t));
mx=max(mx,pre[t]);
//cout <<pre[t]<<" "<<t<<" "<<i<<" chk1"<<endl;
}
else
{
pre[t]=0;
}
}
sort(vt.rbegin(),vt.rend());
for (int j=1;j<=s;j++)
{
dp[i][j]=pre1[j-1][i-mx];
/*if (i<=3)
{
cout <<dp[i][j]<<" "<<i<<" "<<j<<" chk"<<endl;
}*/
for (ll t=0;t<vt.size();t++)
{
ll k=t;
while (k<vt.size()&&vt[k].ff==vt[t].ff) k++;
k--;
ll nxt=0;
if (k+1<vt.size()) nxt=vt[k+1].ff;
ll st=i-nxt;
ll valpre=dp[i][j];
dp[i][j]=min(dp[i][j],get(st,j-1,t+1)+(k+1)*f[i]);
t=k;
}
}
}
for (int i=1;i<=s;i++)
{
//dp[n][i]=max(0ll,dp[n][i]);
cout <<dp[n][i]<<endl;
}
}
/*1
10 6
0 9 16
0 6 2
1 5 10 15
*/
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:160:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (ll t=0;t<vt.size();t++)
| ~^~~~~~~~~~
popeala.cpp:163:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | while (k<vt.size()&&vt[k].ff==vt[t].ff) k++;
| ~^~~~~~~~~~
popeala.cpp:166:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | if (k+1<vt.size()) nxt=vt[k+1].ff;
| ~~~^~~~~~~~~~
popeala.cpp:168:20: warning: unused variable 'valpre' [-Wunused-variable]
168 | ll valpre=dp[i][j];
| ^~~~~~
popeala.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen("popeala.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen("popeala.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
50124 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
50424 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
53504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
333 ms |
64120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
50124 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
50424 KB |
Output isn't correct |
