oj.uz

답안 #6007

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6007 2014-06-14T10:30:07 Z model_code 없는 등수 찾기 (GA7_rank) C++
10 / 100
 0 ms 2228 KB 
#include<stdio.h>
#define mod 1000000007

typedef long long lld;

int n, m, r, a[270], b[270];
lld dy1[270][270], dy2[270][270], dap=1;

void countk(int k){
	int i, j;
	lld u1, u2, d;
	dy1[0][0]=dy2[0][0]=1;
	for(i=1; i<=n; i++){
		if(b[i]<k)d=b[i]-a[i]+1, u1=u2=0;
		else if(a[i]>k)u1=u2=b[i]-a[i]+1, d=0;
		else d=k-a[i], u1=b[i]-k+1, u2=b[i]-k;
		for(j=0; j<=i; j++){
			dy1[i][j] = u1*dy1[i-1][j], dy2[i][j] = u2*dy2[i-1][j];
			if(j)dy1[i][j] += d*dy1[i-1][j-1], dy2[i][j] += d*dy2[i-1][j-1];
			dy1[i][j] %= mod, dy2[i][j] %= mod;
		}
	}
	dap -= (dy1[n][r-1]-dy2[n][r-1]);
	dap %= mod;
	if(dap<0)dap += mod;
}

int main(){
	int i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=n; i++)scanf("%d%d", &a[i], &b[i]), dap=dap*(b[i]-a[i]+1)%mod;
	scanf("%d", &r);
	for(i=0; i<=m; i++)countk(i);
	printf("%lld", dap);
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2228 KB Output is correct
2 Correct 0 ms 2228 KB Output is correct
3 Correct 0 ms 2228 KB Output is correct
4 Correct 0 ms 2228 KB Output is correct
5 Correct 0 ms 2228 KB Output is correct
6 Correct 0 ms 2228 KB Output is correct
7 Correct 0 ms 2228 KB Output is correct
8 Correct 0 ms 2228 KB Output is correct
9 Correct 0 ms 2228 KB Output is correct
10 Correct 0 ms 2228 KB Output is correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2228 KB Output isn't correct
2 Halted 0 ms 0 KB -