oj.uz

Submission #404432

# Submission time Handle Problem Language Result Execution time Memory
404432 2021-05-14T12:04:57 Z CursedCode Boat (APIO16_boat) C++14
36 / 100
 701 ms 23348 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 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);
			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 644 ms 23084 KB Output is correct
2 Correct 660 ms 23176 KB Output is correct
3 Correct 681 ms 23236 KB Output is correct
4 Correct 634 ms 23108 KB Output is correct
5 Correct 645 ms 23096 KB Output is correct
6 Correct 557 ms 23180 KB Output is correct
7 Correct 550 ms 23192 KB Output is correct
8 Correct 555 ms 23132 KB Output is correct
9 Correct 585 ms 23232 KB Output is correct
10 Correct 561 ms 23284 KB Output is correct
11 Correct 552 ms 23108 KB Output is correct
12 Correct 567 ms 23348 KB Output is correct
13 Correct 583 ms 23172 KB Output is correct
14 Correct 543 ms 23188 KB Output is correct
15 Correct 572 ms 23176 KB Output is correct
16 Correct 142 ms 10820 KB Output is correct
17 Correct 146 ms 10984 KB Output is correct
18 Correct 145 ms 10868 KB Output is correct
19 Correct 147 ms 11076 KB Output is correct
20 Correct 143 ms 10948 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 23084 KB Output is correct
2 Correct 660 ms 23176 KB Output is correct
3 Correct 681 ms 23236 KB Output is correct
4 Correct 634 ms 23108 KB Output is correct
5 Correct 645 ms 23096 KB Output is correct
6 Correct 557 ms 23180 KB Output is correct
7 Correct 550 ms 23192 KB Output is correct
8 Correct 555 ms 23132 KB Output is correct
9 Correct 585 ms 23232 KB Output is correct
10 Correct 561 ms 23284 KB Output is correct
11 Correct 552 ms 23108 KB Output is correct
12 Correct 567 ms 23348 KB Output is correct
13 Correct 583 ms 23172 KB Output is correct
14 Correct 543 ms 23188 KB Output is correct
15 Correct 572 ms 23176 KB Output is correct
16 Correct 142 ms 10820 KB Output is correct
17 Correct 146 ms 10984 KB Output is correct
18 Correct 145 ms 10868 KB Output is correct
19 Correct 147 ms 11076 KB Output is correct
20 Correct 143 ms 10948 KB Output is correct
21 Incorrect 701 ms 18612 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 3788 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 3788 KB Output is correct
7 Correct 16 ms 3840 KB Output is correct
8 Correct 15 ms 3804 KB Output is correct
9 Correct 15 ms 3872 KB Output is correct
10 Correct 15 ms 3868 KB Output is correct
11 Correct 17 ms 3788 KB Output is correct
12 Correct 14 ms 3804 KB Output is correct
13 Correct 15 ms 3864 KB Output is correct
14 Correct 15 ms 3844 KB Output is correct
15 Correct 15 ms 3788 KB Output is correct
16 Correct 9 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 9 ms 2892 KB Output is correct
20 Correct 9 ms 2764 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 23084 KB Output is correct
2 Correct 660 ms 23176 KB Output is correct
3 Correct 681 ms 23236 KB Output is correct
4 Correct 634 ms 23108 KB Output is correct
5 Correct 645 ms 23096 KB Output is correct
6 Correct 557 ms 23180 KB Output is correct
7 Correct 550 ms 23192 KB Output is correct
8 Correct 555 ms 23132 KB Output is correct
9 Correct 585 ms 23232 KB Output is correct
10 Correct 561 ms 23284 KB Output is correct
11 Correct 552 ms 23108 KB Output is correct
12 Correct 567 ms 23348 KB Output is correct
13 Correct 583 ms 23172 KB Output is correct
14 Correct 543 ms 23188 KB Output is correct
15 Correct 572 ms 23176 KB Output is correct
16 Correct 142 ms 10820 KB Output is correct
17 Correct 146 ms 10984 KB Output is correct
18 Correct 145 ms 10868 KB Output is correct
19 Correct 147 ms 11076 KB Output is correct
20 Correct 143 ms 10948 KB Output is correct
21 Incorrect 701 ms 18612 KB Output isn't correct
22 Halted 0 ms 0 KB -