| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 47098 | 2018-04-27T14:53:05 Z | zscoder | Popeala (CEOI16_popeala) | C++17 | 2000 ms | 23436 KB |
#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;
scanf("%d %d %d",&n,&t,&k);
}
pref[0]=0;
for(int i=1;i<=t;i++)
{
if(DEBUG) a[i]=rand()%20;
else scanf("%lld",a+i);
pref[i]=pref[i-1]+a[i];
}
for(int i=0;i<n;i++)
{
char s[20010];
if(DEBUG)
{
int q=rand()%1000;
for(int j=0;j<t;j++)
{
int p=rand()%1000;
if(p<=q) s[j]='1';
else s[j]+='0';
}
}
else
{
scanf("%s",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;
}
}
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;
//cerr<<"DONE"<<endl;
for(int i = 1; i <= k; i++)
{
for(int j=0;j<i;j++) dp2[i][j]=INF;
deque<int> dq[51];
for(int i=0;i<=n;i++) dq[i].clear();
int lasr[51];
memset(lasr,0,sizeof(lasr));
for(int j = i; j <= t; j++)
{
dp2[i][j]=INF;
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;
while(lasr[sc]<=r)
{
//if(!dq[sc].empty()) cerr<<"FR : "<<dq[sc].front()<<'\n';
while(!dq[sc].empty()&&dp2[i-1][lasr[sc]]-pref[lasr[sc]]*sc<=dp2[i-1][dq[sc].back()]-pref[dq[sc].back()]*sc)
{
//cerr<<"HERE\n";
dq[sc].pop_back();
}
//cerr<<"HERE OUT\n";
dq[sc].pb(lasr[sc]);
//cerr<<"ADD "<<sc<<' '<<lasr<<'\n';
//if(!dq[sc].empty()) cerr<<"FR : "<<dq[sc].front()<<'\n';
//cerr<<lasr<<'\n';
lasr[sc]++;
}
//cerr<<"NORMAL : "<<dq[sc].size()<<' '<<dq[sc].front()<<'\n';
while(!dq[sc].empty()&&dq[sc].front()<l)
{
//cerr<<"HERE\n";
//cerr<<"DEL "<<sc<<' '<<' '<<dq[sc].front()<<endl;
dq[sc].pop_front();
}
//cerr<<dq[sc].size()<<' '<<sc<<' '<<l<<' '<<lasr<<'\n';
int f = dq[sc].front();
//cerr<<"F : "<<f<<'\n';
dp2[i][j]=min(dp2[i][j],dp2[i-1][f]-pref[f]*sc+pref[j]*sc);
//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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 888 KB | Output is correct |
| 2 | Correct | 3 ms | 1256 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 46 ms | 2192 KB | Output is correct |
| 2 | Correct | 43 ms | 2316 KB | Output is correct |
| 3 | Correct | 45 ms | 2548 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 196 ms | 4876 KB | Output is correct |
| 2 | Correct | 313 ms | 6468 KB | Output is correct |
| 3 | Correct | 476 ms | 8152 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 888 KB | Output is correct |
| 2 | Correct | 3 ms | 1256 KB | Output is correct |
| 3 | Correct | 46 ms | 2192 KB | Output is correct |
| 4 | Correct | 43 ms | 2316 KB | Output is correct |
| 5 | Correct | 45 ms | 2548 KB | Output is correct |
| 6 | Correct | 196 ms | 4876 KB | Output is correct |
| 7 | Correct | 313 ms | 6468 KB | Output is correct |
| 8 | Correct | 476 ms | 8152 KB | Output is correct |
| 9 | Correct | 743 ms | 11836 KB | Output is correct |
| 10 | Correct | 1109 ms | 15180 KB | Output is correct |
| 11 | Execution timed out | 2072 ms | 23436 KB | Time limit exceeded |
| 12 | Halted | 0 ms | 0 KB | - |