记录编号	298692	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.218 s
提交时间	2016-08-22 16:00:51	内存使用	5.85 MiB

#include<stdio.h>
#define INF 0x7ffffff
#define Size 10010
#define Sizen 1010
inline void read(int &x)
{
	int flag=1;
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9') if(ch=='-') flag=-1;
	x=ch^'0';
	while(ch=getchar(),ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0');
	x*=flag;
}
inline int Min(int x,int y){return x<y?x:y;}
//================================================================
int Up[Size],Down[Size],Pipe[Size][2],f[Size][Sizen];
int _521()
{
#define STRAT
#ifdef STRAT
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int n,m,k,i,j,ansover=0;
	bool flag;
	read(n),read(m),read(k);
	for(i=1;i<=n;i++) read(Up[i]),read(Down[i]),Pipe[i][0]=-1,Pipe[i][1]=m+1;
	for(i=1;i<=k;i++) read(j),read(Pipe[j][0]),read(Pipe[j][1]);
	for(i=1;i<=n;i++) for(j=0;j<=m;j++) f[i][j]=INF;
    f[0][0]=INF;
	for(i=1;i<=n;i++){
		flag=false;
		for(j=Up[i]+1;j<=m;j++)
			f[i][j]=Min(f[i][j],Min(f[i][j-Up[i]],f[i-1][j-Up[i]])+1);
		for(j=m-Down[i];j>=1;j--)
			f[i][j]=Min(f[i][j],f[i-1][j+Down[i]]);
		for(j=m;j>=m-Up[i];j--)
			f[i][m]=Min(f[i][m],Min(f[i][j],f[i-1][j])+1);
		for(j=0;j<=Pipe[i][0];j++) f[i][j]=INF;
		for(j=m;j>=Pipe[i][1];j--) f[i][j]=INF;
		for(j=1;j<=m;j++) if(f[i][j]<INF) {flag=true;break;}
		if(!flag) break;
		if(Pipe[i][0]!=-1&&Pipe[i][1]!=m+1) ansover++;
	}
	if(!flag){
		printf("0\n%d\n",ansover);
		return 0;
	}
	for(i=1,j=INF;i<=m;i++) j=Min(j,f[n][i]);
	printf("1\n%d\n",j);
	return 0;
}
int _520=_521();
int main(){;}