oj.uz

Submission #403422

# Submission time Handle Problem Language Result Execution time Memory
403422 2021-05-13T07:15:42 Z Bill_00 Boat (APIO16_boat) C++14
36 / 100
 679 ms 23228 KB 
#include <bits/stdc++.h>
#define ll long long
const ll MOD=1000000007;
using namespace std;
ll n,k;
ll l[1005],r[1005],dp[1005][1005],val[1005],cnt[1005][1005],c[1005][1005],sum[1005][1005],len[1005],C[1005][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=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<=min(len[i],n);j++){
			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 679 ms 23076 KB Output is correct
2 Correct 643 ms 23124 KB Output is correct
3 Correct 642 ms 23088 KB Output is correct
4 Correct 636 ms 23092 KB Output is correct
5 Correct 623 ms 23124 KB Output is correct
6 Correct 521 ms 23120 KB Output is correct
7 Correct 514 ms 23176 KB Output is correct
8 Correct 522 ms 23228 KB Output is correct
9 Correct 531 ms 23064 KB Output is correct
10 Correct 525 ms 23180 KB Output is correct
11 Correct 522 ms 23084 KB Output is correct
12 Correct 532 ms 23192 KB Output is correct
13 Correct 539 ms 23112 KB Output is correct
14 Correct 556 ms 23064 KB Output is correct
15 Correct 513 ms 23172 KB Output is correct
16 Correct 136 ms 10792 KB Output is correct
17 Correct 146 ms 11036 KB Output is correct
18 Correct 146 ms 10952 KB Output is correct
19 Correct 149 ms 11080 KB Output is correct
20 Correct 144 ms 10896 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 23076 KB Output is correct
2 Correct 643 ms 23124 KB Output is correct
3 Correct 642 ms 23088 KB Output is correct
4 Correct 636 ms 23092 KB Output is correct
5 Correct 623 ms 23124 KB Output is correct
6 Correct 521 ms 23120 KB Output is correct
7 Correct 514 ms 23176 KB Output is correct
8 Correct 522 ms 23228 KB Output is correct
9 Correct 531 ms 23064 KB Output is correct
10 Correct 525 ms 23180 KB Output is correct
11 Correct 522 ms 23084 KB Output is correct
12 Correct 532 ms 23192 KB Output is correct
13 Correct 539 ms 23112 KB Output is correct
14 Correct 556 ms 23064 KB Output is correct
15 Correct 513 ms 23172 KB Output is correct
16 Correct 136 ms 10792 KB Output is correct
17 Correct 146 ms 11036 KB Output is correct
18 Correct 146 ms 10952 KB Output is correct
19 Correct 149 ms 11080 KB Output is correct
20 Correct 144 ms 10896 KB Output is correct
21 Incorrect 647 ms 18656 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 16 ms 3788 KB Output is correct
2 Correct 14 ms 3836 KB Output is correct
3 Correct 16 ms 3764 KB Output is correct
4 Correct 14 ms 3824 KB Output is correct
5 Correct 15 ms 3844 KB Output is correct
6 Correct 15 ms 3788 KB Output is correct
7 Correct 16 ms 3788 KB Output is correct
8 Correct 15 ms 3868 KB Output is correct
9 Correct 15 ms 3776 KB Output is correct
10 Correct 16 ms 3784 KB Output is correct
11 Correct 15 ms 3848 KB Output is correct
12 Correct 14 ms 3888 KB Output is correct
13 Correct 15 ms 3788 KB Output is correct
14 Correct 17 ms 3788 KB Output is correct
15 Correct 15 ms 3788 KB Output is correct
16 Correct 9 ms 2812 KB Output is correct
17 Correct 9 ms 2764 KB Output is correct
18 Correct 9 ms 2764 KB Output is correct
19 Correct 9 ms 2844 KB Output is correct
20 Correct 9 ms 2768 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 679 ms 23076 KB Output is correct
2 Correct 643 ms 23124 KB Output is correct
3 Correct 642 ms 23088 KB Output is correct
4 Correct 636 ms 23092 KB Output is correct
5 Correct 623 ms 23124 KB Output is correct
6 Correct 521 ms 23120 KB Output is correct
7 Correct 514 ms 23176 KB Output is correct
8 Correct 522 ms 23228 KB Output is correct
9 Correct 531 ms 23064 KB Output is correct
10 Correct 525 ms 23180 KB Output is correct
11 Correct 522 ms 23084 KB Output is correct
12 Correct 532 ms 23192 KB Output is correct
13 Correct 539 ms 23112 KB Output is correct
14 Correct 556 ms 23064 KB Output is correct
15 Correct 513 ms 23172 KB Output is correct
16 Correct 136 ms 10792 KB Output is correct
17 Correct 146 ms 11036 KB Output is correct
18 Correct 146 ms 10952 KB Output is correct
19 Correct 149 ms 11080 KB Output is correct
20 Correct 144 ms 10896 KB Output is correct
21 Incorrect 647 ms 18656 KB Output isn't correct
22 Halted 0 ms 0 KB -