oj.uz

답안 #6840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6840 2014-07-08T05:36:47 Z qja0950 없는 등수 찾기 (GA7_rank) C++
30 / 100
 1500 ms 3088 KB 
#include <stdio.h>

#define MAXN 292
#define MOD 1000000007

int N, M, R;
int A[MAXN], B[MAXN];
void INPUT() {
	scanf("%d %d", &N, &M);
	for(int i=1; i<=N; i++)
		scanf("%d %d", &A[i], &B[i]);
	scanf("%d", &R);
}
long long Dy[2][MAXN][MAXN];
int Check[2][MAXN][MAXN];
void PROCESS() {
	long long Ans=0;
	for(int p=0; p<=M; p++) {
		for(int t0=0; t0<2; t0++)
			for(int t1=0; t1<=N; t1++)
				for(int t2=0; t2<=N; t2++)
					Dy[t0][t1][t2]=0;
		Dy[0][0][0]=1;
		for(int i=1; i<=N; i++) {
			int over, same, under;
			if(A[i]<=p && p<=B[i]) over=B[i]-p;
			else if(p<A[i]) over=B[i]-A[i]+1;
			else over=0;

			if(A[i]<=p && p<=B[i]) under=p-A[i];
			else if(B[i]<p) under=B[i]-A[i]+1;
			else under=0;


			if(A[i]<=p && p<=B[i]) same=1;
			else same=0;

			for(int j=0; j<=N; j++) {
				for(int k=0; k<=N; k++) {
					Dy[i%2][j][k]=Dy[1-i%2][j][k]*(long long) under;
					Dy[i%2][j][k]%=MOD;
				}
			}
			for(int j=0; j<=N; j++) {
				for(int k=0; k<=N; k++) {
					Dy[i%2][j+1][k]+=Dy[1-i%2][j][k]*(long long)over;
					Dy[i%2][j+1][k]%=MOD;

					Dy[i%2][j][k+1]+=Dy[1-i%2][j][k]*(long long)same;
					Dy[i%2][j][k+1]%=MOD;
				}
			}
		}
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=N; j++) {
				if(i<R-1 && i+j>=R && j>=2) {
					Ans+=Dy[N%2][i][j];
					Ans%=MOD;
				}
			}
		}
	}
	printf("%lld\n", Ans);
}
int main() {
//	freopen("input", "r", stdin);
	INPUT();
	PROCESS();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3088 KB Output is correct
2 Correct 68 ms 3088 KB Output is correct
3 Correct 52 ms 3088 KB Output is correct
4 Correct 216 ms 3088 KB Output is correct
5 Correct 1132 ms 3088 KB Output is correct
6 Execution timed out 1500 ms 3084 KB Program timed out
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3088 KB Output is correct
2 Correct 68 ms 3088 KB Output is correct
3 Correct 48 ms 3088 KB Output is correct
4 Correct 216 ms 3088 KB Output is correct
5 Correct 1128 ms 3088 KB Output is correct
6 Execution timed out 1500 ms 3084 KB Program timed out
7 Halted 0 ms 0 KB -