记录编号	546206	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	0.698 s
提交时间	2019-11-07 13:52:19	内存使用	52.42 MiB

#include<bits/stdc++.h>
#define maxn 10010
#define maxm 1010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,a[maxn],b[maxn],a1[maxn],a2[maxn],f1,f2,f3,bk[maxn],f[maxn][maxm],ans=inf;
int main(){
	freopen("birda.in","r",stdin);
	freopen("birda.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++)a1[i]=1,a2[i]=m;
	for(int i=1;i<=k;i++){
	    scanf("%d%d%d",&f1,&f2,&f3);
		a1[f1]=f2+1,a2[f1]=f3-1;bk[f1]=1;
	}
	for(int i=1;i<=n;i++){
		if(!bk[i])bk[i]=bk[i-1];
		else bk[i]=bk[i-1]+1;
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++)f[0][i]=0;
	for(int i=1;i<=n;i++){
		for(int j=1+a[i];j<=m;j++)f[i][j]=min(f[i][j],min(f[i][j-a[i]],f[i-1][j-a[i]])+1);
		for(int j=m-a[i];j<=m;j++)f[i][m]=min(f[i][m],min(f[i-1][j],f[i][j])+1);
		for(int j=0;j<a1[i];j++)f[i][j]=inf;
		for(int j=a2[i]+1;j<=m;j++)f[i][j]=inf;
		for(int j=a1[i];j<=a2[i];j++)if(j+b[i]<=m)f[i][j]=min(f[i][j],f[i-1][j+b[i]]);
	}
	for(int i=1;i<=m;i++)ans=min(ans,f[n][i]);
	if(ans==inf){
		printf("0\n");
		for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)if(f[i][j]!=inf){printf("%d\n",bk[i]);return 0;}
	}
	printf("1\n%d",ans);
}