Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

bitset + O2优化 32ms

Posted by ACAccepted at 2019-02-11 19:18:04 on Problem 2436 and last updated at 2019-02-11 19:18:33
#include <cstdio>
#include <bitset>
#pragma GCC optimize(2)
%:pragma GCC optimize(2)                                    //O2优化,选其一即可。
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=1010;
const int MAXD=20;
int n,d,k,m,ans;
bitset<MAXD> cow[MAXN];
bitset<MAXD> down;

void dfs(int vis,int now,bitset<MAXD> down)
{
	if (now+d-vis+1<k)return ;
	if (now==k)
	{
		int res=0;
		bitset<MAXD> a;
		for (int i=1;i<=n;i++)
		{
			a=down&cow[i];
			if (a==cow[i])res++;
		}
		if (res>ans)ans=res;
		return ;
	}
	for (int i=vis;i<=d;i++)
	{
		down[i]=1;
		dfs(i+1,now+1,down);
		down[i]=0;
	}
}

int main()
{
	n=read();d=read();k=read();
	for (int i=1;i<=n;i++)
	{
		m=read();
		while (m--)cow[i].set(read());
	}
	ans=0;
	dfs(1,0,down);
	printf("%d\n",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator