답안 #6052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6052 2014-06-15T21:04:40 Z ainta 없는 등수 찾기 (GA7_rank) C++
100 / 100
696 ms 2072 KB
#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, R;
int w[251][2];
long long R1, R2, Mod = 1000000007, D[2][251][251];
void Do(int x){
	int i, j, k;
	for (i = 0; i <= n; i++){
		for (j = 0; j < R; j++){
			D[0][i][j] = D[1][i][j] = 0;
		}
	}
	D[0][0][0] = 1;
	for (i = 1; i <= n; i++){
		for (j = 0; j < R; j++){
			if (!D[0][i - 1][j] && !D[1][i - 1][j])continue;
			D[0][i - 1][j] %= Mod;
			D[1][i - 1][j] %= Mod;
			if (w[i][0] <= x && x <= w[i][1] && j != R-1){
				D[1][i][j + 1] = D[1][i][j + 1] + D[0][i - 1][j] + D[1][i - 1][j];
			}
			for (k = 0; k < 2; k++){
				if (w[i][0] < x){
					D[k][i][j] = D[k][i][j] + D[k][i - 1][j] * (min(x - 1, w[i][1]) - w[i][0] + 1);
				}
				if (w[i][1] > x && j != R - 1){
					D[k][i][j + 1] = D[k][i][j + 1] + D[k][i - 1][j] * (w[i][1] - max(w[i][0], x + 1) + 1);
				}
			}
		}
	}
	R2 = (R2 + D[1][n][R - 1]) % Mod;
	for (i = 0; i <= n; i++){
		for (j = 0; j < R; j++){
			D[0][i][j] = D[1][i][j] = 0;
		}
	}
}
int main()
{
	int i;
	scanf("%d%d", &n, &m);
	R1 = 1;
	for (i = 1; i <= n; i++){
		scanf("%d%d", &w[i][0], &w[i][1]);
		R1 = R1*(w[i][1] - w[i][0] + 1) % Mod;
	}
	scanf("%d", &R);
	if (R == 1){
		printf("0\n");
		return 0;
	}
	for (i = 0; i <= m; i++){
		Do(i);
	}
	printf("%lld\n", (R1 - R2 + Mod) % Mod);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 0 ms 2072 KB Output is correct
3 Correct 0 ms 2072 KB Output is correct
4 Correct 0 ms 2072 KB Output is correct
5 Correct 0 ms 2072 KB Output is correct
6 Correct 0 ms 2072 KB Output is correct
7 Correct 0 ms 2072 KB Output is correct
8 Correct 0 ms 2072 KB Output is correct
9 Correct 0 ms 2072 KB Output is correct
10 Correct 0 ms 2072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 0 ms 2072 KB Output is correct
3 Correct 0 ms 2072 KB Output is correct
4 Correct 0 ms 2072 KB Output is correct
5 Correct 0 ms 2072 KB Output is correct
6 Correct 0 ms 2072 KB Output is correct
7 Correct 0 ms 2072 KB Output is correct
8 Correct 0 ms 2072 KB Output is correct
9 Correct 0 ms 2072 KB Output is correct
10 Correct 0 ms 2072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 0 ms 2072 KB Output is correct
3 Correct 0 ms 2072 KB Output is correct
4 Correct 0 ms 2072 KB Output is correct
5 Correct 0 ms 2072 KB Output is correct
6 Correct 0 ms 2072 KB Output is correct
7 Correct 0 ms 2072 KB Output is correct
8 Correct 0 ms 2072 KB Output is correct
9 Correct 0 ms 2072 KB Output is correct
10 Correct 0 ms 2072 KB Output is correct
11 Correct 0 ms 2072 KB Output is correct
12 Correct 0 ms 2072 KB Output is correct
13 Correct 0 ms 2072 KB Output is correct
14 Correct 0 ms 2072 KB Output is correct
15 Correct 0 ms 2072 KB Output is correct
16 Correct 0 ms 2072 KB Output is correct
17 Correct 4 ms 2072 KB Output is correct
18 Correct 4 ms 2072 KB Output is correct
19 Correct 0 ms 2072 KB Output is correct
20 Correct 8 ms 2072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Correct 0 ms 2072 KB Output is correct
3 Correct 0 ms 2072 KB Output is correct
4 Correct 8 ms 2072 KB Output is correct
5 Correct 20 ms 2072 KB Output is correct
6 Correct 28 ms 2072 KB Output is correct
7 Correct 24 ms 2072 KB Output is correct
8 Correct 80 ms 2072 KB Output is correct
9 Correct 0 ms 2072 KB Output is correct
10 Correct 48 ms 2072 KB Output is correct
11 Correct 40 ms 2072 KB Output is correct
12 Correct 12 ms 2072 KB Output is correct
13 Correct 112 ms 2072 KB Output is correct
14 Correct 32 ms 2072 KB Output is correct
15 Correct 124 ms 2072 KB Output is correct
16 Correct 192 ms 2072 KB Output is correct
17 Correct 196 ms 2072 KB Output is correct
18 Correct 0 ms 2072 KB Output is correct
19 Correct 352 ms 2072 KB Output is correct
20 Correct 696 ms 2072 KB Output is correct