#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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
ll a[20001];
ll pref[20001];
ll dp2[51][20001];
const ll INF = ll(1e18);
bool solve[51][20001];
ll dp[51][20001];
int cnt[51][20001];
vector<pair<pair<int,int>,int> > opt[20001];
ll st[51][16][20001];
ll query(int sc, int l, int r)
{
int z = 31 - __builtin_clz(r-l);
if(l==r) z=0;
//cerr<<l<<' '<<r-(1<<z)+1<<' '<<st[sc][z][l]<<' '<<st[sc][z][r-(1<<z)+1]<<'\n';
return min(st[sc][z][l],st[sc][z][r-(1<<z)+1]);
}
const bool DEBUG = 0;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
srand(12301);
//srand(time(NULL));
//freopen("popeala.in","r",stdin);
int T = int(1e9);
if(!DEBUG) T=1;
for(int cc=1;cc<=T;cc++)
{
int n,t,k;
//cin>>n>>t>>k;
if(DEBUG)
{
n=40;
t=rand()%50+2;
k=min(50,t);
}
else
{
cin>>n>>t>>k;
}
pref[0]=0;
for(int i=1;i<=t;i++)
{
if(DEBUG) a[i]=rand()%20;
else cin>>a[i];
pref[i]=pref[i-1]+a[i];
}
for(int i=0;i<n;i++)
{
string s;
if(DEBUG)
{
int q=rand()%1000;
for(int j=0;j<t;j++)
{
int p=rand()%1000;
if(p<=q) s+='1';
else s+='0';
}
}
else
{
cin>>s;
}
cnt[i][0]=0;
for(int j=1;j<=t;j++)
{
solve[i][j]=s[j-1]-'0';
cnt[i][j]=cnt[i][j-1];
if(!solve[i][j])
{
cnt[i][j]++;
}
}
}
if(DEBUG)
{
dp[0][0]=0;
for(int i=1;i<=k;i++) dp[i][0]=INF;
for(int i=1;i<=t;i++) dp[0][i]=INF;
}
for(int i = 1; i <= t; i++)
{
opt[i].clear();
int r = i - 1;
while(r>=0)
{
int lo = 0; int hi = r;
int ans = 0; int sc = 0;
for(int j=0;j<n;j++)
{
if(cnt[j][i]==cnt[j][r])
{
sc++;
}
}
while(lo<=hi)
{
int mid = (lo+hi)>>1;
int sc2=0;
for(int j=0;j<n;j++)
{
if(cnt[j][i]==cnt[j][mid])
{
sc2++;
}
}
if(sc2==sc)
{
ans=mid;
hi=mid-1;
}
else lo=mid+1;
}
opt[i].pb(mp(mp(ans,r),sc));
r=ans-1;
}
/*
for(int j = i - 1; j >= 1; j--)
{
bool die=0;
for(int k=0;k<n;k++)
{
if(valid&(1LL<<k))
{
if(!solve[k][j])
{
valid^=(1LL<<k);
die=1;
}
}
}
if(die)
{
opt[i].pb(mp(mp(j,r),__builtin_popcountll(valid2))); //the previous one
r=j-1;
valid2=valid;
}
}
opt[i].pb(mp(mp(0,r),__builtin_popcountll(valid2)));
*/
}
if(DEBUG)
{
for(int i = 1; i <= k; i++)
{
for(int j = 1; j <= t; j++)
{
dp[i][j]=INF;
for(int k = 0; k < j; k++)
{
ll sc=0;
for(int l = 0; l < n; l++)
{
if(cnt[l][j]==cnt[l][k])
{
sc+=pref[j]-pref[k];
}
}
if(sc+dp[i-1][k]<dp[i][j])
{
dp[i][j]=sc+dp[i-1][k];
}
}
}
}
}
dp2[0][0]=0;
for(int i=1;i<=k;i++) dp2[i][0]=INF;
for(int i=1;i<=t;i++) dp2[0][i]=INF;
for(int i = 1; i <= k; i++)
{
for(int sc = 0; sc <= n; sc++)
{
for(int j = 0; j < 15; j++)
{
for(int k = 0; k <= t; k++)
{
if(j==0)
{
st[sc][j][k] = dp2[i-1][k] - pref[k]*sc;
//cerr<<sc<<' '<<j<<' '<<k<<' '<<st[sc][j][k]<<'\n';
}
else
{
if(k+(1<<(j-1))<=t) st[sc][j][k]=min(st[sc][j-1][k],st[sc][j-1][k+(1<<(j-1))]);
else st[sc][j][k] = st[sc][j-1][k];
}
}
}
}
for(int j=0;j<i;j++) dp2[i][j]=INF;
for(int j = i; j <= t; j++)
{
dp2[i][j]=INF;
/*
for(int z = 0; z < opt[j].size(); z++)
{
int k = opt[j][z].fi.se;
//cerr<<j<<' '<<opt[j][z].fi.fi<<' '<<opt[j][z].fi.se<<' '<<opt[j][z].se<<'\n';
//cerr<<k<<' '<<i<<' '<<j<<'\n';
ll sc=0;
for(int l = 0; l < n; l++)
{
if(cnt[l][j]==cnt[l][k])
{
sc+=pref[j]-pref[k];
}
}
if(sc+dp[i-1][k]<dp2[i][j])
{
dp2[i][j]=sc+dp2[i-1][k];
}
k = opt[j][z].fi.fi;
//cerr<<k<<' '<<i<<' '<<j<<'\n';
sc=0;
for(int l = 0; l < n; l++)
{
if(cnt[l][j]==cnt[l][k])
{
sc+=pref[j]-pref[k];
}
}
if(sc+dp[i-1][k]<dp2[i][j])
{
dp2[i][j]=sc+dp2[i-1][k];
}
}
*/
for(int z = 0; z < opt[j].size(); z++)
{
int l = opt[j][z].fi.fi; int r = opt[j][z].fi.se;
int sc = opt[j][z].se;
dp2[i][j] = min(dp2[i][j],query(sc,l,r)+pref[j]*sc);
//cerr<<i<<' '<<j<<' '<<sc<<' '<<l<<' '<<r<<' '<<dp2[i][j]<<'\n';
/*
for(int k=l;k<=r;k++)
{
dp2[i][j]=min(dp2[i][j],dp2[i-1][k]-pref[k]*sc+pref[j]*sc);
}
*/
}
}
}
if(DEBUG)
{
bool pos=1;
for(int i=1;i<=k;i++)
{
if(dp[i][t]!=dp2[i][t]) pos=0;
//cout<<dp[i][t]<<' '<<dp2[i][t]<<' '<<dp2[i][t]-dp[i][t]<<'\n';
}
if(!pos)
{
cerr<<"FAIL\n";
freopen("popeala.in","w",stdout);
cout<<n<<' '<<t<<' '<<k<<'\n';
for(int i=1;i<=t;i++) cout<<a[i]<<' ';
cout<<'\n';
for(int i=0;i<n;i++)
{
for(int j=1;j<=t;j++)
{
cout<<solve[i][j];
}
cout<<'\n';
}
return 0;
}
cerr<<"Case #"<<cc<<" complete\n";
}
else
{
for(int i=1;i<=k;i++)
{
cout<<dp2[i][t]<<'\n';
}
}
}
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:252:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int z = 0; z < opt[j].size(); z++)
^
popeala.cpp:278:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("popeala.in","w",stdout);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
151388 KB |
Output is correct |
| 2 |
Correct |
0 ms |
151388 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
151652 KB |
Output is correct |
| 2 |
Correct |
56 ms |
151652 KB |
Output is correct |
| 3 |
Correct |
63 ms |
151652 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
346 ms |
152840 KB |
Output is correct |
| 2 |
Correct |
426 ms |
153500 KB |
Output is correct |
| 3 |
Correct |
536 ms |
154292 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
151388 KB |
Output is correct |
| 2 |
Correct |
0 ms |
151388 KB |
Output is correct |
| 3 |
Correct |
59 ms |
151652 KB |
Output is correct |
| 4 |
Correct |
56 ms |
151652 KB |
Output is correct |
| 5 |
Correct |
63 ms |
151652 KB |
Output is correct |
| 6 |
Correct |
346 ms |
152840 KB |
Output is correct |
| 7 |
Correct |
426 ms |
153500 KB |
Output is correct |
| 8 |
Correct |
536 ms |
154292 KB |
Output is correct |
| 9 |
Correct |
1093 ms |
156140 KB |
Output is correct |
| 10 |
Correct |
1273 ms |
157724 KB |
Output is correct |
| 11 |
Execution timed out |
2000 ms |
166172 KB |
Execution timed out |
| 12 |
Halted |
0 ms |
0 KB |
- |
