1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<algorithm>
#include<cstdio>

const int N = 1000001;
const int P = 1000000007;
int availableSince[N];
int possibleWays[N];
int maxTeams[N];
int c[N];
int d[N];
int main(){
	int n;
	scanf("%d", &n);
	maxTeams[0] = 0;
	possibleWays[0] = 1;
	for(int i = 0; i < n; i++)
		scanf("%d%d", &c[i], &d[i]);
	int minc = *std::min_element(c, c + n);
	int maxd = *std::max_element(d, d + n);
	for(int i = 1; i <= n; i++){
		std::fill(availableSince + minc, availableSince + c[i - 1], i);
		std::fill(availableSince + d[i - 1] + 1, availableSince + maxd + 1, i);
		int maxTeams0 = -N;
		for(int j = c[i - 1]; j <= d[i - 1]; j++)
			if(availableSince[j] <= i - j)
				maxTeams0 = std::max(maxTeams0, maxTeams[i - j]);
		maxTeams[i] = maxTeams0;
		if(maxTeams0 >= 0){
			for(int j = c[i - 1]; j <= d[i - 1]; j++)
				if(availableSince[j] <= i - j && maxTeams[i - j] == maxTeams0){
					possibleWays[i] += possibleWays[i - j];
					if(possibleWays[i] >= P)
						possibleWays[i] -= P;
				}	
			maxTeams[i]++;
		}
	}
	if(maxTeams[n] > 0)
		printf("%d %d\n", maxTeams[n], possibleWays[n]);
	else
		printf("NIE\n");
	return 0;
}