oj.uz

Submission #403355

# Submission time Handle Problem Language Result Execution time Memory
403355 2021-05-13T05:19:15 Z Bill_00 Boat (APIO16_boat) C++14
9 / 100
 622 ms 16284 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]*(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;
				sum[i][j]=sum[i][j-1]+c[i][j];
				if(sum[i][j]>=MOD) sum[i][j]%=MOD;
			}
			// cout << i << ' ' << j << ' ' << c[i][j] << '\n';
		}
	}
	for(int i=1;i<=k;i++){
		// cout << val[i] << ' ';
	}
	// cout << "\n";
	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(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;
				// 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 309 ms 16224 KB Output is correct
2 Correct 320 ms 16232 KB Output is correct
3 Correct 311 ms 16180 KB Output is correct
4 Correct 302 ms 16168 KB Output is correct
5 Correct 307 ms 16120 KB Output is correct
6 Correct 203 ms 16172 KB Output is correct
7 Correct 252 ms 16172 KB Output is correct
8 Correct 208 ms 16184 KB Output is correct
9 Correct 214 ms 16192 KB Output is correct
10 Correct 204 ms 16196 KB Output is correct
11 Correct 207 ms 16204 KB Output is correct
12 Correct 208 ms 16220 KB Output is correct
13 Correct 205 ms 16136 KB Output is correct
14 Correct 207 ms 16120 KB Output is correct
15 Correct 209 ms 16284 KB Output is correct
16 Correct 65 ms 8132 KB Output is correct
17 Correct 66 ms 8436 KB Output is correct
18 Correct 74 ms 8296 KB Output is correct
19 Correct 69 ms 8460 KB Output is correct
20 Correct 69 ms 8280 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 16224 KB Output is correct
2 Correct 320 ms 16232 KB Output is correct
3 Correct 311 ms 16180 KB Output is correct
4 Correct 302 ms 16168 KB Output is correct
5 Correct 307 ms 16120 KB Output is correct
6 Correct 203 ms 16172 KB Output is correct
7 Correct 252 ms 16172 KB Output is correct
8 Correct 208 ms 16184 KB Output is correct
9 Correct 214 ms 16192 KB Output is correct
10 Correct 204 ms 16196 KB Output is correct
11 Correct 207 ms 16204 KB Output is correct
12 Correct 208 ms 16220 KB Output is correct
13 Correct 205 ms 16136 KB Output is correct
14 Correct 207 ms 16120 KB Output is correct
15 Correct 209 ms 16284 KB Output is correct
16 Correct 65 ms 8132 KB Output is correct
17 Correct 66 ms 8436 KB Output is correct
18 Correct 74 ms 8296 KB Output is correct
19 Correct 69 ms 8460 KB Output is correct
20 Correct 69 ms 8280 KB Output is correct
21 Incorrect 622 ms 15808 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 16224 KB Output is correct
2 Correct 320 ms 16232 KB Output is correct
3 Correct 311 ms 16180 KB Output is correct
4 Correct 302 ms 16168 KB Output is correct
5 Correct 307 ms 16120 KB Output is correct
6 Correct 203 ms 16172 KB Output is correct
7 Correct 252 ms 16172 KB Output is correct
8 Correct 208 ms 16184 KB Output is correct
9 Correct 214 ms 16192 KB Output is correct
10 Correct 204 ms 16196 KB Output is correct
11 Correct 207 ms 16204 KB Output is correct
12 Correct 208 ms 16220 KB Output is correct
13 Correct 205 ms 16136 KB Output is correct
14 Correct 207 ms 16120 KB Output is correct
15 Correct 209 ms 16284 KB Output is correct
16 Correct 65 ms 8132 KB Output is correct
17 Correct 66 ms 8436 KB Output is correct
18 Correct 74 ms 8296 KB Output is correct
19 Correct 69 ms 8460 KB Output is correct
20 Correct 69 ms 8280 KB Output is correct
21 Incorrect 622 ms 15808 KB Output isn't correct
22 Halted 0 ms 0 KB -