#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define pb push_back
#define EPS 1e-9
const int INF = 2000000009;
const int MOD = 1000000007; // 998244353
const int MX_t = 20003 , MX_n = 53;
int n,t,s,p[MX_t],A[MX_t][MX_n],dp[MX_n][MX_t],pre[MX_n][MX_t],par[MX_t];
string S;
vii ranges[MX_n][MX_t];
int find_set(int i){
if(par[i]==i)return i;
return par[i]=find_set(par[i]);
}
int32_t main(){
boost;
//freopen(".in","r",stdin);
cin>>n>>t>>s;
for (int i = 1; i <= t; ++i)
{
cin>>p[i];
if(i)p[i]+=p[i-1];
}
for (int i = 0; i < n; ++i)
{
cin>>S;
for (int j = 1; j <= t; ++j)
{
if(S[j-1]=='0')A[j][i]=j;
else A[j][i]=A[j-1][i];
}
}
for (int i = 1; i <= t; ++i)
{
A[i][n]=i;
sort(A[i],A[i]+n+1);
}
for (int i = 0; i < MX_n; ++i)
for (int j = 0; j <= t; ++j)
dp[i][j]=INF,pre[i][j]=INF;
dp[0][0]=0;
for (int j = 1; j <= t; ++j)
{
if(A[j][0])ranges[0][A[j][0]].pb({1,j});
for (int i = 0; i <= n; ++i)
if((A[j][i]+1) <= A[j][i+1])
ranges[i+1][A[j][i+1]].pb({A[j][i]+1,j});
}
for (int k = 1; k <= s; ++k)
{
for (int x = 0; x <= n; ++x)
{
stack<int> st;
for (int j = 1; j <= t; ++j)
par[j]=j;
for (int j = 1; j <= t; ++j)
{
int val;
if(dp[k-1][j-1]!=INF)val=dp[k-1][j-1]-p[j-1]*x;
else val=INF;
while(!st.empty() && ((dp[k-1][st.top()-1]==INF)?INF:(dp[k-1][st.top()-1]-p[st.top()-1]*x)) > val){
par[st.top()]=j;
st.pop();
}
st.push(j);
for(auto it:ranges[x][j]){
int h=find_set(it.fi);
if(dp[k-1][h-1]!=INF)pre[x][it.se]=dp[k-1][h-1]-p[h-1]*x;
else pre[x][it.se]=INF;
}
}
}
for (int j = 1; j <= t; ++j)
for (int x = 0; x <= n; ++x)
if(pre[x][j]!=INF)dp[k][j]=min(dp[k][j],pre[x][j]+p[j]*x);
cout<<dp[k][t]<<"\n";
}
return 0;
}
//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25728 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
26368 KB |
Output is correct |
| 2 |
Correct |
49 ms |
26360 KB |
Output is correct |
| 3 |
Correct |
50 ms |
26368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
28664 KB |
Output is correct |
| 2 |
Correct |
230 ms |
29816 KB |
Output is correct |
| 3 |
Correct |
304 ms |
30968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
25728 KB |
Output is correct |
| 2 |
Correct |
19 ms |
25856 KB |
Output is correct |
| 3 |
Correct |
51 ms |
26368 KB |
Output is correct |
| 4 |
Correct |
49 ms |
26360 KB |
Output is correct |
| 5 |
Correct |
50 ms |
26368 KB |
Output is correct |
| 6 |
Correct |
163 ms |
28664 KB |
Output is correct |
| 7 |
Correct |
230 ms |
29816 KB |
Output is correct |
| 8 |
Correct |
304 ms |
30968 KB |
Output is correct |
| 9 |
Correct |
492 ms |
33656 KB |
Output is correct |
| 10 |
Correct |
753 ms |
36728 KB |
Output is correct |
| 11 |
Correct |
1379 ms |
50168 KB |
Output is correct |
| 12 |
Correct |
1409 ms |
50692 KB |
Output is correct |
| 13 |
Correct |
1640 ms |
50612 KB |
Output is correct |
| 14 |
Correct |
1673 ms |
50552 KB |
Output is correct |
| 15 |
Correct |
1663 ms |
50612 KB |
Output is correct |
