记录编号	447338	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.430 s
提交时间	2017-09-10 08:33:52	内存使用	48.14 MiB

#include<cstdio>
#include<cstring>
#define INF 1000000000
#define syy myson
using namespace std;
const int maxn=10001,maxm=1001;
int n,m,kk,p,l,h,ans=INF,cnt,i,j,k;
int f[maxn][maxm],up[maxn],down[maxn],sum[maxn];
bool pic[maxn][maxm];
int min(int a,int b)
{
	return a<b?a:b;
}
int Min(int a,int b,int c)
{
	return min(a,min(b,c));
}
int Main()
{
	freopen("birda.in","r",stdin);freopen("birda.out","w",stdout);
	memset(f,127,sizeof(f));
	memset(pic,true,sizeof(pic));
	scanf("%d%d%d",&n,&m,&kk);
	for(i=0;i<n;i++)scanf("%d%d",&up[i],&down[i]);
	for(i=1;i<=kk;i++)
	{
		scanf("%d%d%d",&p,&l,&h);
		for(j=0;j<=l;j++)pic[p][j]=0;
		for(j=h;j<=m;j++)pic[p][j]=0;
		sum[p]=INF;
	}
	for(i=0;i<=n;i++)
	{
		pic[i][0]=0;
		if(sum[i]==INF)cnt++;
		sum[i]=cnt;
	}
	for(i=1;i<=m;i++)if(pic[0][i])f[0][i]=0;
	for(i=1;i<=n;i++)
	{
		for(j=up[i-1]+1;j<=m;j++)
			f[i][j]=Min(f[i][j],f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1);
		for(j=m-up[i-1];j<=m;j++)
			f[i][m]=Min(f[i][m],f[i-1][j]+1,f[i][j]+1);
		for(j=1;j+down[i-1]<=m;j++)
			f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
		for(j=1;j<=m;j++)
			if(!pic[i][j])f[i][j]=INF;
	}
	for(i=1;i<=m;i++)ans=min(ans,f[n][i]);
	if(ans!=INF)printf("1\n%d\n",ans);
	else
	{
		for(i=n;i>=1;i--)for(j=1;j<=m;j++)
		if(f[i][j]<INF)
		{
			printf("0\n%d\n",sum[i]);
			return 0;
		}
	}
	return 0;
}
int main(){;}
int syy=Main();