oj.uz

Submission #30672

# Submission time Handle Problem Language Result Execution time Memory
30672 2017-07-26T05:11:31 Z zscoder Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 38800 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;
		}
		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;
			}
		}
		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 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;
						}
						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;
			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

popeala.cpp: In function 'int main()':
popeala.cpp:203:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int z = 0; z < opt[j].size(); z++)
                      ^
popeala.cpp:255: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);
                                     ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23884 KB Output is correct
2 Correct 0 ms 23884 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 24148 KB Output is correct
2 Correct 33 ms 24148 KB Output is correct
3 Correct 46 ms 24148 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 25336 KB Output is correct
2 Correct 279 ms 26128 KB Output is correct
3 Correct 379 ms 26920 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23884 KB Output is correct
2 Correct 0 ms 23884 KB Output is correct
3 Correct 43 ms 24148 KB Output is correct
4 Correct 33 ms 24148 KB Output is correct
5 Correct 46 ms 24148 KB Output is correct
6 Correct 159 ms 25336 KB Output is correct
7 Correct 279 ms 26128 KB Output is correct
8 Correct 379 ms 26920 KB Output is correct
9 Correct 633 ms 28636 KB Output is correct
10 Correct 779 ms 30220 KB Output is correct
11 Execution timed out 2000 ms 38800 KB Execution timed out
12 Halted 0 ms 0 KB -