记录编号	176168	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	1.965 s
提交时间	2015-08-08 06:59:32	内存使用	38.86 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#define  maxn  10005UL
#define  maxm  1005UL
#define  infi  0x3f3f3f3f

int n,m,k;
int up[maxn] = {0} , down[maxn] = {0} ;
int L[maxn] = {0} , R[maxn] = {0} ;
int f[maxn][maxm] = {0} ;
int flag[maxn] = {0} ;
int cnt = 0 ;
int main() {
	freopen("birda.in" ,"r",stdin ) ;
	freopen("birda.out","w",stdout) ;
	int p;
	std::cin>>n>>m>>k;
	for (int i = 0 ; i < n ; i ++ ) {
		std::cin>>up[i]>>down[i];
	}
	for (int i = 1 ; i <= k ; i ++ ) {
		std::cin>>p>>L[i]>>R[i];
		flag[p] = i ;
	}
	memset(f , 0x3f , sizeof (f)) ;
	memset(f[0] , 0 , sizeof (f[0])) ;
	int i , j , k , t ;
	bool False = false ;
	for (i = 1 ; i <= n ; i ++ ) {
		False = true ;
		if (flag[i]) {
			cnt ++ ;
			for (j = 1 ; j < R[flag[i]] ; j ++ ) {
				if (j-up[i-1] < 1) continue ;
				if (f[i-1][j-up[i-1]]+1 < f[i][j]) f[i][j] = f[i-1][j-up[i-1]]+1 ;
				if (f[i][j-up[i-1]]+1 < f[i][j]) f[i][j] = f[i][j-up[i-1]]+1 ;
				if (j>L[flag[i]] && f[i][j]!=infi) False = false ;
			}
			for (j = L[flag[i]]+1 ; j < R[flag[i]] ; j ++ ) {
				if (j+down[i-1] > m) break ;
				if (f[i-1][j+down[i-1]] < f[i][j]) f[i][j] = f[i-1][j+down[i-1]] ;
				if (f[i][j] != infi) False = false ;
			}
			for (j = 1 ; j <= L[flag[i]] ; j ++ ) f[i][j] = infi ;
		} else {
			for (j = up[i-1]+1 ; j <= m ; j ++ ) {
				if (j-up[i-1] < 1) continue ;
				if (f[i-1][j-up[i-1]]+1 < f[i][j]) f[i][j] = f[i-1][j-up[i-1]]+1 ;
				if (f[i][j-up[i-1]]+1 < f[i][j]) f[i][j] = f[i][j-up[i-1]]+1 ;
				if (f[i][j] != infi) False = false ;
			}
			for (j = 1 ; j < m ; j ++ ) {
				if (j+down[i-1] > m) break ;
				if (f[i-1][j+down[i-1]] < f[i][j]) f[i][j] = f[i-1][j+down[i-1]] ;
				if (f[i][j] != infi) False = false ;
			}
			for (j = m-up[i-1]+1 ; j <= m ; j ++ ) {
				if (j < 1) continue ;
				if (f[i-1][j]+1 < f[i][m]) f[i][m] = f[i-1][j]+1 ;
				if (f[i][j]+1 < f[i][m]) f[i][m] = f[i][j]+1 ;
				if (f[i][m] != infi) False = false ;
			}
		}
		if (False) {
			std::cout<<0<<'\n'<<cnt-1;
			return 0;
		}
	}
	cnt = infi ;
	for (i = 1 ; i <= m ; i ++ ) if (f[n][i] < cnt) cnt = f[n][i] ;
	std::cout<<1<<'\n'<<cnt;
	return 0 ;
}