oj.uz

Submission #163030

# Submission time Handle Problem Language Result Execution time Memory
163030 2019-11-11T03:37:20 Z HungAnhGoldIBO2020 Boat (APIO16_boat) C++14
0 / 100
 6 ms 392 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=502;
const int mod=1e9+7;
int used[N],sum[N],dp[N],ndp[N],choose[N],rev[N];
vector<pair<int,int> > ope;
int binpow(int x,int y){
	int tich=1;
	while(y){
		if(y&1){
			tich*=x;
			tich%=mod;
		}
		x*=x;
		x%=mod;
		y>>=1;
	}
	return tich;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>j>>k;
		k++;
		ope.push_back({j,i});
		ope.push_back({k,i});
	}
	sort(ope.begin(),ope.end());
	rev[0]=1;
	for(i=1;i<=n;i++){
		rev[i]=binpow(i,mod-2);
	}
	i=0;
	j=0;
	dp[0]=1;
	while(i<ope.size()){
		while(j<ope.size()&&ope[j].first==ope[i].first){
			used[ope[j].second]^=1;
			j++;
		}
		if(j==ope.size()){
			break;
		}
		for(k=1;k<=n;k++){
			sum[k]=sum[k-1]+used[k];
			choose[k]=0;
		}
		int len=ope[j].first-ope[i].first,val=sum[n],c1,c2;
		//cout<<len<<' '<<val<<endl;
		for(k=1;k<=min(len,val);k++){
			c1=len;
			c2=1;
			choose[k]=0;
			for(l=0;l<k;l++){
				choose[k]+=c1*c2;
				choose[k]%=mod;
				c1=c1*(len-l-1);
				c1%=mod;
				c1=c1*rev[l+2];
				c1%=mod;
				c2=c2*(k-l-1);
				c2%=mod;
				c2=c2*rev[l+1];
				c2%=mod;
			}
		//	cout<<choose[k]<<endl;
		}
		ndp[0]=1;
		for(k=1;k<=n;k++){
			ndp[k]=dp[k];
			if(used[k]){
				for(l=0;l<k;l++){
					ndp[k]+=dp[l]*choose[sum[k]-sum[l]];
					ndp[k]%=mod;
				}
			}
		}
		for(k=0;k<=n;k++){
			dp[k]=ndp[k];
		//	cout<<dp[k]<<' ';
		}
		//cout<<endl;
		i=j;
	}
	int ans=0;
	for(i=1;i<=n;i++){
		ans+=dp[i];
		if(ans>=mod){
			ans-=mod;
		}
	}
	cout<<ans;
}
/*
3
1 2
3 4
5 6
3
1 2
4 5
7 8
26
*/

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<ope.size()){
        ~^~~~~~~~~~~
boat.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<ope.size()&&ope[j].first==ope[i].first){
         ~^~~~~~~~~~~
boat.cpp:45:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(j==ope.size()){
      ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 392 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 392 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 392 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -