oj.uz

Submission #403413

# Submission time Handle Problem Language Result Execution time Memory
403413 2021-05-13T07:05:31 Z Bill_00 Boat (APIO16_boat) C++14
36 / 100
 619 ms 18284 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],C[505][505];
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=0;i<=n;i++){
		C[i][0]=1;
		for(ll j=1;j<=i;j++){
			C[i][j]=C[i][j-1]*(i+1-j);
			if(C[i][j]>=MOD) C[i][j]%=MOD;
			C[i][j]*=power(j,MOD-2);
			if(C[i][j]>=MOD) C[i][j]%=MOD;
		}
	}
	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]*(len[i]+1-j);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
				c[i][j]*=power(j,MOD-2);
				if(c[i][j]>=MOD) c[i][j]%=MOD;
			}
			// cout << i << ' ' << j << ' ' << c[i][j] << '\n';
		}
	}
	for(ll i=1;i<k;i++){
		for(ll j=1;j<=min(len[i],n);j++){
			ll res=0;
			for(ll t=1;t<=j;t++){
				res+=(c[i][t]*C[j-1][t-1]);
				if(res>=MOD) res%=MOD;
			}
			sum[i][j]=res;
		}
	}
	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];
			// cout << i << ' ' << j << ' ' << cnt[i][j] << '\n';
		}
	}
	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(l[t+1]<=val[j] && val[j]<=r[t+1]){
					ll p=cnt[i][j]-cnt[t][j];
					dp[i][j]+=(dp[t][j-1]*sum[j][min(p,len[j])]);
					if(dp[i][j]>=MOD) dp[i][j]%=MOD;
				}
				// if(i==1 && j==2) cout << cnt[i][j] << '\n';
			}
			// cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	cout << (dp[n][k-1]-1+MOD)%MOD;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 18128 KB Output is correct
2 Correct 519 ms 18192 KB Output is correct
3 Correct 537 ms 18284 KB Output is correct
4 Correct 520 ms 18124 KB Output is correct
5 Correct 521 ms 18228 KB Output is correct
6 Correct 401 ms 18180 KB Output is correct
7 Correct 413 ms 18256 KB Output is correct
8 Correct 407 ms 18220 KB Output is correct
9 Correct 415 ms 18116 KB Output is correct
10 Correct 407 ms 18196 KB Output is correct
11 Correct 396 ms 18148 KB Output is correct
12 Correct 428 ms 18204 KB Output is correct
13 Correct 402 ms 18184 KB Output is correct
14 Correct 408 ms 18192 KB Output is correct
15 Correct 417 ms 18116 KB Output is correct
16 Correct 142 ms 10212 KB Output is correct
17 Correct 144 ms 10416 KB Output is correct
18 Correct 138 ms 10288 KB Output is correct
19 Correct 143 ms 10444 KB Output is correct
20 Correct 147 ms 10304 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 18128 KB Output is correct
2 Correct 519 ms 18192 KB Output is correct
3 Correct 537 ms 18284 KB Output is correct
4 Correct 520 ms 18124 KB Output is correct
5 Correct 521 ms 18228 KB Output is correct
6 Correct 401 ms 18180 KB Output is correct
7 Correct 413 ms 18256 KB Output is correct
8 Correct 407 ms 18220 KB Output is correct
9 Correct 415 ms 18116 KB Output is correct
10 Correct 407 ms 18196 KB Output is correct
11 Correct 396 ms 18148 KB Output is correct
12 Correct 428 ms 18204 KB Output is correct
13 Correct 402 ms 18184 KB Output is correct
14 Correct 408 ms 18192 KB Output is correct
15 Correct 417 ms 18116 KB Output is correct
16 Correct 142 ms 10212 KB Output is correct
17 Correct 144 ms 10416 KB Output is correct
18 Correct 138 ms 10288 KB Output is correct
19 Correct 143 ms 10444 KB Output is correct
20 Correct 147 ms 10304 KB Output is correct
21 Incorrect 619 ms 17804 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3788 KB Output is correct
2 Correct 14 ms 3788 KB Output is correct
3 Correct 14 ms 3752 KB Output is correct
4 Correct 14 ms 3788 KB Output is correct
5 Correct 14 ms 3788 KB Output is correct
6 Correct 16 ms 3768 KB Output is correct
7 Correct 15 ms 3740 KB Output is correct
8 Correct 15 ms 3796 KB Output is correct
9 Correct 15 ms 3788 KB Output is correct
10 Correct 15 ms 3788 KB Output is correct
11 Correct 15 ms 3788 KB Output is correct
12 Correct 14 ms 3796 KB Output is correct
13 Correct 15 ms 3736 KB Output is correct
14 Correct 14 ms 3712 KB Output is correct
15 Correct 14 ms 3756 KB Output is correct
16 Correct 9 ms 2764 KB Output is correct
17 Correct 9 ms 2764 KB Output is correct
18 Correct 8 ms 2764 KB Output is correct
19 Correct 8 ms 2764 KB Output is correct
20 Correct 8 ms 2764 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 18128 KB Output is correct
2 Correct 519 ms 18192 KB Output is correct
3 Correct 537 ms 18284 KB Output is correct
4 Correct 520 ms 18124 KB Output is correct
5 Correct 521 ms 18228 KB Output is correct
6 Correct 401 ms 18180 KB Output is correct
7 Correct 413 ms 18256 KB Output is correct
8 Correct 407 ms 18220 KB Output is correct
9 Correct 415 ms 18116 KB Output is correct
10 Correct 407 ms 18196 KB Output is correct
11 Correct 396 ms 18148 KB Output is correct
12 Correct 428 ms 18204 KB Output is correct
13 Correct 402 ms 18184 KB Output is correct
14 Correct 408 ms 18192 KB Output is correct
15 Correct 417 ms 18116 KB Output is correct
16 Correct 142 ms 10212 KB Output is correct
17 Correct 144 ms 10416 KB Output is correct
18 Correct 138 ms 10288 KB Output is correct
19 Correct 143 ms 10444 KB Output is correct
20 Correct 147 ms 10304 KB Output is correct
21 Incorrect 619 ms 17804 KB Output isn't correct
22 Halted 0 ms 0 KB -