oj.uz

Submission #6048

# Submission time Handle Problem Language Result Execution time Memory
6048 2014-06-15T20:50:08 Z ainta 없는 등수 찾기 (GA7_rank) C++
10 / 100
 0 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 (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]) % Mod;
			}
			for (k = 0; k < 2; k++){
				if (w[i][0] < x && j != R - 1){
					D[k][i][j + 1] = (D[k][i][j + 1] + D[k][i - 1][j] * (min(x - 1, w[i][1]) - w[i][0] + 1)) % Mod;
				}
				if (w[i][1] > x){
					D[k][i][j] = (D[k][i][j] + D[k][i - 1][j] * (w[i][1] - max(w[i][0], x + 1) + 1)) % Mod;
				}
			}
		}
	}
	R2 = (R2 + D[1][n][R - 1]) % Mod;
}
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 = 1; i <= m; i++){
		Do(i);
	}
	printf("%lld\n", (R1 - R2 + Mod) % Mod);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2072 KB Output is correct
2 Incorrect 0 ms 2072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2072 KB Output isn't correct
2 Halted 0 ms 0 KB -