oj.uz

Submission #404447

# Submission time Handle Problem Language Result Execution time Memory
404447 2021-05-14T12:18:41 Z CursedCode Boat (APIO16_boat) C++14
36 / 100
 660 ms 23340 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 a, ll b){
    if(b<=0)return 1;
    ll g=power(a,b/2);
    g=(g*g)%MOD;
    if(b%2)g=(g*a)%MOD;
    return g;
}
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 660 ms 23108 KB Output is correct
2 Correct 659 ms 23300 KB Output is correct
3 Correct 660 ms 23176 KB Output is correct
4 Correct 657 ms 23340 KB Output is correct
5 Correct 655 ms 23116 KB Output is correct
6 Correct 543 ms 23204 KB Output is correct
7 Correct 537 ms 23152 KB Output is correct
8 Correct 544 ms 23188 KB Output is correct
9 Correct 547 ms 23140 KB Output is correct
10 Correct 541 ms 23092 KB Output is correct
11 Correct 541 ms 23232 KB Output is correct
12 Correct 548 ms 23208 KB Output is correct
13 Correct 535 ms 23168 KB Output is correct
14 Correct 535 ms 23104 KB Output is correct
15 Correct 548 ms 23108 KB Output is correct
16 Correct 152 ms 10692 KB Output is correct
17 Correct 160 ms 11020 KB Output is correct
18 Correct 155 ms 10872 KB Output is correct
19 Correct 160 ms 11004 KB Output is correct
20 Correct 159 ms 10960 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 23108 KB Output is correct
2 Correct 659 ms 23300 KB Output is correct
3 Correct 660 ms 23176 KB Output is correct
4 Correct 657 ms 23340 KB Output is correct
5 Correct 655 ms 23116 KB Output is correct
6 Correct 543 ms 23204 KB Output is correct
7 Correct 537 ms 23152 KB Output is correct
8 Correct 544 ms 23188 KB Output is correct
9 Correct 547 ms 23140 KB Output is correct
10 Correct 541 ms 23092 KB Output is correct
11 Correct 541 ms 23232 KB Output is correct
12 Correct 548 ms 23208 KB Output is correct
13 Correct 535 ms 23168 KB Output is correct
14 Correct 535 ms 23104 KB Output is correct
15 Correct 548 ms 23108 KB Output is correct
16 Correct 152 ms 10692 KB Output is correct
17 Correct 160 ms 11020 KB Output is correct
18 Correct 155 ms 10872 KB Output is correct
19 Correct 160 ms 11004 KB Output is correct
20 Correct 159 ms 10960 KB Output is correct
21 Incorrect 469 ms 18632 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 17 ms 3872 KB Output is correct
3 Correct 16 ms 3788 KB Output is correct
4 Correct 17 ms 3788 KB Output is correct
5 Correct 17 ms 3788 KB Output is correct
6 Correct 18 ms 3788 KB Output is correct
7 Correct 17 ms 3788 KB Output is correct
8 Correct 17 ms 3788 KB Output is correct
9 Correct 17 ms 3788 KB Output is correct
10 Correct 17 ms 3788 KB Output is correct
11 Correct 17 ms 3788 KB Output is correct
12 Correct 17 ms 3844 KB Output is correct
13 Correct 17 ms 3812 KB Output is correct
14 Correct 17 ms 3804 KB Output is correct
15 Correct 17 ms 3788 KB Output is correct
16 Correct 9 ms 2784 KB Output is correct
17 Correct 9 ms 2816 KB Output is correct
18 Correct 9 ms 2764 KB Output is correct
19 Correct 9 ms 2824 KB Output is correct
20 Correct 9 ms 2716 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 23108 KB Output is correct
2 Correct 659 ms 23300 KB Output is correct
3 Correct 660 ms 23176 KB Output is correct
4 Correct 657 ms 23340 KB Output is correct
5 Correct 655 ms 23116 KB Output is correct
6 Correct 543 ms 23204 KB Output is correct
7 Correct 537 ms 23152 KB Output is correct
8 Correct 544 ms 23188 KB Output is correct
9 Correct 547 ms 23140 KB Output is correct
10 Correct 541 ms 23092 KB Output is correct
11 Correct 541 ms 23232 KB Output is correct
12 Correct 548 ms 23208 KB Output is correct
13 Correct 535 ms 23168 KB Output is correct
14 Correct 535 ms 23104 KB Output is correct
15 Correct 548 ms 23108 KB Output is correct
16 Correct 152 ms 10692 KB Output is correct
17 Correct 160 ms 11020 KB Output is correct
18 Correct 155 ms 10872 KB Output is correct
19 Correct 160 ms 11004 KB Output is correct
20 Correct 159 ms 10960 KB Output is correct
21 Incorrect 469 ms 18632 KB Output isn't correct
22 Halted 0 ms 0 KB -