记录编号	140591	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014]飞扬的小鸟	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.750 s
提交时间	2014-11-22 19:59:42	内存使用	34.95 MiB

#include <cstdio>
#include <cstring>

#define  maxn  10005LL
#define  maxm  1005LL
#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 ;

void dp() {
	memset(f , 0x3f , sizeof (f)) ;
	memset(f[0] , 0 , sizeof (f[0])) ;
	int i , j , k , p , 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) {
			printf("0\n%d\n", cnt-1 ) ; return ;
		}
	}
	cnt = infi ;
	for (i = 1 ; i <= m ; i ++ ) if (f[n][i] < cnt) cnt = f[n][i] ;
	printf("1\n%d\n", cnt ) ;
}

int main() {
	    freopen("birda.in" ,"r",stdin ) ;
	    freopen("birda.out","w",stdout) ;
	int i , p ;
	scanf("%d%d%d", &n , &m , &k ) ;
	for (i = 0 ; i < n ; i ++ ) {
		scanf("%d%d", &up[i] , &down[i] ) ;
	}
	for (i = 1 ; i <= k ; i ++ ) {
		scanf("%d%d%d", &p , &L[i] , &R[i] ) ;
		flag[p] = i ;
	}
	dp() ;
	    fclose(stdin ) ; fclose(stdout) ;
	return 0 ;
}
/*
10 10 6
3 9
9 9
1 2
1 3
1 2
1 1
2 1
2 1
1 6
2 2
1 2 7
5 1 5
6 3 5
7 5 8
8 7 9
9 1 3
*/
/*
10 10 4
1 2
3 1
2 2
1 8
1 8
3 2
2 1
2 1
2 2
1 2
1 0 2
6 7 9
9 1 4
3 8 10
*/