oj.uz

Submission #745222

# Submission time Handle Problem Language Result Execution time Memory
745222 2023-05-19T15:07:40 Z amirhoseinfar1385 Boat (APIO16_boat) C++17
9 / 100
 1244 ms 5576 KB 
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
const int maxn=501;
long long dp[maxn*3][maxn];
long long ps[maxn*3];
int rev[maxn+10];

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<=n+5;i++){
		rev[i]=mypow(i,mod-2);
	}
	vector<pair<int,int>>all(n+1);
	vector<int>allind;
	for(int i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
		allind.push_back(all[i].first);
		allind.push_back(all[i].second);
		allind.push_back(all[i].first-1);
	}
	allind.push_back(0);
	sort(allind.begin(),allind.end());
	allind.resize(unique(allind.begin(),allind.end())-allind.begin());
	int sz=(int)allind.size()+1;
	dp[0][0]=1;
	for(int i=0;i<sz+10;i++){
		ps[i]=1;
	}
	for(int i=1;i<=n;i++){
		int l=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin();
		int r=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin();
		for(int j=l;j<=r;j++){
			int cnt=allind[j]-allind[j-1];
			for(int h=n;h>=2;h--){
				dp[j][h]+=(dp[j][h]+dp[j][h-1]*(cnt-(h-1)))%mod*rev[h]%mod;
			}
			dp[j][1]=(dp[j][1]+ps[j-1]*cnt)%mod;
		}
		ps[0]=dp[0][0];
		for(int i=1;i<=sz+9;i++){
			ps[i]=ps[i-1];
			for(int h=0;h<=n;h++){
				ps[i]+=dp[i][h];
			}
			ps[i]%=mod;
		}
	}
	long long res=ps[sz+8];
	res+=mod-1;
	res%=mod;
	cout<<res<<"\n";
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4180 KB Output is correct
2 Correct 135 ms 4184 KB Output is correct
3 Correct 133 ms 4208 KB Output is correct
4 Correct 136 ms 4192 KB Output is correct
5 Correct 144 ms 4260 KB Output is correct
6 Correct 154 ms 4204 KB Output is correct
7 Correct 134 ms 4236 KB Output is correct
8 Correct 129 ms 4260 KB Output is correct
9 Correct 138 ms 4288 KB Output is correct
10 Correct 142 ms 4256 KB Output is correct
11 Correct 142 ms 4172 KB Output is correct
12 Correct 130 ms 4180 KB Output is correct
13 Correct 130 ms 4148 KB Output is correct
14 Correct 134 ms 4172 KB Output is correct
15 Correct 156 ms 4236 KB Output is correct
16 Correct 32 ms 1004 KB Output is correct
17 Correct 38 ms 1064 KB Output is correct
18 Correct 29 ms 1000 KB Output is correct
19 Correct 30 ms 1104 KB Output is correct
20 Correct 27 ms 1004 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4180 KB Output is correct
2 Correct 135 ms 4184 KB Output is correct
3 Correct 133 ms 4208 KB Output is correct
4 Correct 136 ms 4192 KB Output is correct
5 Correct 144 ms 4260 KB Output is correct
6 Correct 154 ms 4204 KB Output is correct
7 Correct 134 ms 4236 KB Output is correct
8 Correct 129 ms 4260 KB Output is correct
9 Correct 138 ms 4288 KB Output is correct
10 Correct 142 ms 4256 KB Output is correct
11 Correct 142 ms 4172 KB Output is correct
12 Correct 130 ms 4180 KB Output is correct
13 Correct 130 ms 4148 KB Output is correct
14 Correct 134 ms 4172 KB Output is correct
15 Correct 156 ms 4236 KB Output is correct
16 Correct 32 ms 1004 KB Output is correct
17 Correct 38 ms 1064 KB Output is correct
18 Correct 29 ms 1000 KB Output is correct
19 Correct 30 ms 1104 KB Output is correct
20 Correct 27 ms 1004 KB Output is correct
21 Incorrect 1244 ms 5576 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4180 KB Output is correct
2 Correct 135 ms 4184 KB Output is correct
3 Correct 133 ms 4208 KB Output is correct
4 Correct 136 ms 4192 KB Output is correct
5 Correct 144 ms 4260 KB Output is correct
6 Correct 154 ms 4204 KB Output is correct
7 Correct 134 ms 4236 KB Output is correct
8 Correct 129 ms 4260 KB Output is correct
9 Correct 138 ms 4288 KB Output is correct
10 Correct 142 ms 4256 KB Output is correct
11 Correct 142 ms 4172 KB Output is correct
12 Correct 130 ms 4180 KB Output is correct
13 Correct 130 ms 4148 KB Output is correct
14 Correct 134 ms 4172 KB Output is correct
15 Correct 156 ms 4236 KB Output is correct
16 Correct 32 ms 1004 KB Output is correct
17 Correct 38 ms 1064 KB Output is correct
18 Correct 29 ms 1000 KB Output is correct
19 Correct 30 ms 1104 KB Output is correct
20 Correct 27 ms 1004 KB Output is correct
21 Incorrect 1244 ms 5576 KB Output isn't correct
22 Halted 0 ms 0 KB -