oj.uz

Submission #6838

# Submission time Handle Problem Language Result Execution time Memory
6838 2014-07-08T05:18:58 Z qja0950 없는 등수 찾기 (GA7_rank) C++
0 / 100
 64 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-1; j++) {
				for(int k=0; k<=N-1; 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 && i+j>=R && j>=2) {
					Ans+=Dy[N%2][i][j];
					Ans%=MOD;
				}
			}
		}
	}
	printf("%lld\n", Ans);
}
int main() {
	INPUT();
	PROCESS();
}

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 20.0

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

Subtask #3
0.0 / 30.0

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

Subtask #4
0.0 / 40.0

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