oj.uz

Submission #404438

# Submission time Handle Problem Language Result Execution time Memory
404438 2021-05-14T12:13:32 Z CursedCode Boat (APIO16_boat) C++14
36 / 100
 679 ms 23364 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(){
	cin >> n;
	for(ll i=1;i<=n;i++){
		cin >> l[i] >> r[i];
		s.insert(l[i]);
		s.insert(r[i]+1);
		um[l[i]] = um[r[i] + 1] = 0;
	}
	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);
			C[i][j]%=MOD;
			C[i][j]*=power(j,MOD-2);
			C[i][j]%=MOD;
		}
	}
	for (ll j=0;j<k;j++) c[0][j] = 1;
	for (ll j=0;j<k;j++) C[0][j] = 1;
	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);
			c[i][j]%=MOD;
			c[i][j]*=power(j,MOD-2);
			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]);
				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];
			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])]);
					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;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 23108 KB Output is correct
2 Correct 661 ms 23108 KB Output is correct
3 Correct 635 ms 23292 KB Output is correct
4 Correct 679 ms 23064 KB Output is correct
5 Correct 622 ms 23180 KB Output is correct
6 Correct 513 ms 23128 KB Output is correct
7 Correct 505 ms 23108 KB Output is correct
8 Correct 513 ms 23144 KB Output is correct
9 Correct 508 ms 23108 KB Output is correct
10 Correct 511 ms 23268 KB Output is correct
11 Correct 509 ms 23240 KB Output is correct
12 Correct 514 ms 23104 KB Output is correct
13 Correct 509 ms 23228 KB Output is correct
14 Correct 505 ms 23132 KB Output is correct
15 Correct 507 ms 23364 KB Output is correct
16 Correct 136 ms 10764 KB Output is correct
17 Correct 142 ms 10980 KB Output is correct
18 Correct 138 ms 10820 KB Output is correct
19 Correct 145 ms 11028 KB Output is correct
20 Correct 141 ms 10988 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 23108 KB Output is correct
2 Correct 661 ms 23108 KB Output is correct
3 Correct 635 ms 23292 KB Output is correct
4 Correct 679 ms 23064 KB Output is correct
5 Correct 622 ms 23180 KB Output is correct
6 Correct 513 ms 23128 KB Output is correct
7 Correct 505 ms 23108 KB Output is correct
8 Correct 513 ms 23144 KB Output is correct
9 Correct 508 ms 23108 KB Output is correct
10 Correct 511 ms 23268 KB Output is correct
11 Correct 509 ms 23240 KB Output is correct
12 Correct 514 ms 23104 KB Output is correct
13 Correct 509 ms 23228 KB Output is correct
14 Correct 505 ms 23132 KB Output is correct
15 Correct 507 ms 23364 KB Output is correct
16 Correct 136 ms 10764 KB Output is correct
17 Correct 142 ms 10980 KB Output is correct
18 Correct 138 ms 10820 KB Output is correct
19 Correct 145 ms 11028 KB Output is correct
20 Correct 141 ms 10988 KB Output is correct
21 Incorrect 469 ms 18680 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 3796 KB Output is correct
3 Correct 14 ms 3864 KB Output is correct
4 Correct 14 ms 3836 KB Output is correct
5 Correct 14 ms 3780 KB Output is correct
6 Correct 15 ms 3788 KB Output is correct
7 Correct 15 ms 3872 KB Output is correct
8 Correct 15 ms 3764 KB Output is correct
9 Correct 16 ms 3788 KB Output is correct
10 Correct 15 ms 3788 KB Output is correct
11 Correct 15 ms 3880 KB Output is correct
12 Correct 14 ms 3804 KB Output is correct
13 Correct 15 ms 3764 KB Output is correct
14 Correct 15 ms 3888 KB Output is correct
15 Correct 14 ms 3788 KB Output is correct
16 Correct 8 ms 2892 KB Output is correct
17 Correct 8 ms 2764 KB Output is correct
18 Correct 8 ms 2764 KB Output is correct
19 Correct 8 ms 2892 KB Output is correct
20 Correct 8 ms 2728 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 23108 KB Output is correct
2 Correct 661 ms 23108 KB Output is correct
3 Correct 635 ms 23292 KB Output is correct
4 Correct 679 ms 23064 KB Output is correct
5 Correct 622 ms 23180 KB Output is correct
6 Correct 513 ms 23128 KB Output is correct
7 Correct 505 ms 23108 KB Output is correct
8 Correct 513 ms 23144 KB Output is correct
9 Correct 508 ms 23108 KB Output is correct
10 Correct 511 ms 23268 KB Output is correct
11 Correct 509 ms 23240 KB Output is correct
12 Correct 514 ms 23104 KB Output is correct
13 Correct 509 ms 23228 KB Output is correct
14 Correct 505 ms 23132 KB Output is correct
15 Correct 507 ms 23364 KB Output is correct
16 Correct 136 ms 10764 KB Output is correct
17 Correct 142 ms 10980 KB Output is correct
18 Correct 138 ms 10820 KB Output is correct
19 Correct 145 ms 11028 KB Output is correct
20 Correct 141 ms 10988 KB Output is correct
21 Incorrect 469 ms 18680 KB Output isn't correct
22 Halted 0 ms 0 KB -