oj.uz

답안 #42614

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42614 2018-03-01T12:57:49 Z fefe Boat (APIO16_boat) C++14
9 / 100
 427 ms 5372 KB 
#include<bits/stdc++.h>
#define MAX_N 505
#define mod 1000000007LL
#define pb push_back
typedef long long LL;
using namespace std;
struct node{
	LL s,e;
}arr[MAX_N];
LL n,ans,inv[3*MAX_N];
LL t[3*MAX_N][MAX_N],sum[3*MAX_N][MAX_N],ss[MAX_N];
vector<LL> X,lst;
LL Pow(LL x,LL y){
	if(y==0)	return 1;
	if(y==1)	return x;
	LL z=pow(x,y/2);
	z*=z;z%=mod;
	if(y%2)	z*=x;
	z%=mod;
	return z;
}
int main(){
	LL i,j,k,s,e,x,y,S,E,cnt,p;
	scanf("%lld",&n);
	for(i=1;i<=n;i++){
		scanf("%lld %lld",&arr[i].s,&arr[i].e);
		X.pb(arr[i].s);X.pb(arr[i].e);
	}
	for(i=1;i<=1000;i++)	inv[i]=Pow(i,mod-2);
	sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
	LL sz=X.size();
	for(i=0;i<=n;i++)	sum[0][i]=1;
	for(i=1;i<=sz;i++){
		s=X[i-1];
		if(i-sz)	e=X[i]-1;
		else	e=X[i-1];
		lst.resize(0);
		for(j=1;j<=n;j++){
			if(arr[j].s>e || arr[j].e<s);
			else	lst.pb(j);
		}
		p=e-s+1;
		y=lst.size();
		for(k=0;k<=y;k++){
			for(j=0;j<=y;j++)	t[k][j]=0;
		}
		for(k=0;k<y;k++)	t[1][k]=sum[i-1][lst[k]-1];
		if(p!=1){
			for(k=2;k<y;k++){
				ss[0]=(p*t[k-1][0])%mod;
				for(j=1;j<y;j++)	ss[j]=(ss[j-1]+p*t[k-1][j]%mod)%mod;
				for(j=k-1;j<y;j++){
					if(k>p)	t[k][j]=0;
					else	t[k][j]=((ss[j-1]*(p-k+1))%mod*inv[k])%mod;
				}
			}
		}
		for(j=0;j<y;j++){
			ss[j]=0;
			for(k=0;k<=y;k++)	ss[j]=(ss[j]+t[k][j])%mod;
		}
		sum[i][0]=1;
		x=0;
		for(j=1;j<=n;j++){
			sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mod)%mod;
			if(x!=y && lst[x]==j){
				sum[i][j]=(sum[i][j]+ss[x])%mod;
				x++;
			}
		}
	}
	printf("%lld\n",(sum[sz][n]-1+mod)%mod);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:23:19: warning: unused variable 'S' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                   ^
boat.cpp:23:21: warning: unused variable 'E' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                     ^
boat.cpp:23:23: warning: unused variable 'cnt' [-Wunused-variable]
  LL i,j,k,s,e,x,y,S,E,cnt,p;
                       ^
boat.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
boat.cpp:26:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&arr[i].s,&arr[i].e);
                                         ^

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2296 KB Output is correct
2 Correct 7 ms 2400 KB Output is correct
3 Correct 6 ms 2400 KB Output is correct
4 Correct 6 ms 2400 KB Output is correct
5 Correct 7 ms 2488 KB Output is correct
6 Correct 6 ms 2488 KB Output is correct
7 Correct 6 ms 2488 KB Output is correct
8 Correct 6 ms 2488 KB Output is correct
9 Correct 6 ms 2524 KB Output is correct
10 Correct 6 ms 2524 KB Output is correct
11 Correct 6 ms 2524 KB Output is correct
12 Correct 6 ms 2524 KB Output is correct
13 Correct 6 ms 2532 KB Output is correct
14 Correct 6 ms 2604 KB Output is correct
15 Correct 6 ms 2604 KB Output is correct
16 Correct 3 ms 2604 KB Output is correct
17 Correct 3 ms 2604 KB Output is correct
18 Correct 3 ms 2604 KB Output is correct
19 Correct 3 ms 2604 KB Output is correct
20 Correct 3 ms 2604 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2296 KB Output is correct
2 Correct 7 ms 2400 KB Output is correct
3 Correct 6 ms 2400 KB Output is correct
4 Correct 6 ms 2400 KB Output is correct
5 Correct 7 ms 2488 KB Output is correct
6 Correct 6 ms 2488 KB Output is correct
7 Correct 6 ms 2488 KB Output is correct
8 Correct 6 ms 2488 KB Output is correct
9 Correct 6 ms 2524 KB Output is correct
10 Correct 6 ms 2524 KB Output is correct
11 Correct 6 ms 2524 KB Output is correct
12 Correct 6 ms 2524 KB Output is correct
13 Correct 6 ms 2532 KB Output is correct
14 Correct 6 ms 2604 KB Output is correct
15 Correct 6 ms 2604 KB Output is correct
16 Correct 3 ms 2604 KB Output is correct
17 Correct 3 ms 2604 KB Output is correct
18 Correct 3 ms 2604 KB Output is correct
19 Correct 3 ms 2604 KB Output is correct
20 Correct 3 ms 2604 KB Output is correct
21 Incorrect 427 ms 5372 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2296 KB Output is correct
2 Correct 7 ms 2400 KB Output is correct
3 Correct 6 ms 2400 KB Output is correct
4 Correct 6 ms 2400 KB Output is correct
5 Correct 7 ms 2488 KB Output is correct
6 Correct 6 ms 2488 KB Output is correct
7 Correct 6 ms 2488 KB Output is correct
8 Correct 6 ms 2488 KB Output is correct
9 Correct 6 ms 2524 KB Output is correct
10 Correct 6 ms 2524 KB Output is correct
11 Correct 6 ms 2524 KB Output is correct
12 Correct 6 ms 2524 KB Output is correct
13 Correct 6 ms 2532 KB Output is correct
14 Correct 6 ms 2604 KB Output is correct
15 Correct 6 ms 2604 KB Output is correct
16 Correct 3 ms 2604 KB Output is correct
17 Correct 3 ms 2604 KB Output is correct
18 Correct 3 ms 2604 KB Output is correct
19 Correct 3 ms 2604 KB Output is correct
20 Correct 3 ms 2604 KB Output is correct
21 Incorrect 427 ms 5372 KB Output isn't correct
22 Halted 0 ms 0 KB -