oj.uz

Submission #403338

# Submission time Handle Problem Language Result Execution time Memory
403338 2021-05-13T04:31:22 Z Bill_00 Boat (APIO16_boat) C++14
0 / 100
 313 ms 16196 KB 
#include <bits/stdc++.h>
#define ll long long
const ll MOD=1000000007;
using namespace std;
ll n,k;
ll l[505],r[505],dp[505][1005],val[1005],cnt[505][1005],c[505][1005],sum[505][1005],len[1005];
unordered_map<ll,ll>um;
set<ll>s;
ll power(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1){
			res=res*x;
			if(res>=MOD) res%=MOD;
		}
		y>>=1;
		x=x*x;
		if(x>=MOD) x%=MOD;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(ll i=1;i<=n;i++){
		cin >> l[i] >> r[i];
		s.insert(l[i]);
		s.insert(r[i]+1);
	}
	for(auto i=s.begin();i!=s.end();++i){
		um[*i]=++k;
		val[k]=*i;
		if(k>1) len[k-1]=val[k]-val[k-1];
	}
	for(ll i=1;i<k;i++){
		c[i][0]=1;
		for(ll j=1;j<=n;j++){
			if(j>len[i]) sum[i][j]=sum[i][j-1];
			else{	
				c[i][j]=c[i][j-1]*(n+1-j);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
				c[i][j]*=power(i,MOD-2);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
				sum[i][j]=sum[i][j-1]+c[i][j];
				if(sum[i][j]>=MOD) sum[i][j]%=MOD;
			}
		}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<k;j++){
			if(l[i]<=val[j] && val[j]<r[i]){
				cnt[i][j]=cnt[i-1][j]+1;
			}
			else cnt[i][j]=cnt[i-1][j];
		}
	}
	for(ll i=0;i<=n;i++) dp[i][0]=1;
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<k;j++){
			dp[i][j]+=dp[i][j-1];
			if(dp[i][j]>=MOD) dp[i][j]%=MOD;
			for(ll t=0;t<i;t++){
				if(val[j+1]<=l[t+1] || r[t+1]<val[j]) continue;
				ll p=cnt[i][j]-cnt[t][j];
				dp[i][j]+=(dp[t][j-1]*sum[j][p]);
				if(dp[i][j]>=MOD) dp[i][j]%=MOD;
			}
		}
	}
	cout << dp[n][k-1];
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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