Submission #30669

#	Time	Username	Problem	Language	Result	Execution time	Memory
30669		zscoder	Popeala (CEOI16_popeala)	C++14	26 / 100	2000 ms	166172 KiB

popeala

#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 (stderr)

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);
                                     ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74