oj.uz

답안 #745231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745231 2023-05-19T15:13:49 Z amirhoseinfar1385 Boat (APIO16_boat) C++17
9 / 100
 872 ms 4288 KB 
#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
const int maxn=501;
long long dp[maxn*2+10][maxn+2];
long long ps[maxn*2+10];
int rev[maxn+10];
pair<int,int>all[maxn+10];
vector<int>allind;

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);
	}
	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].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

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 4240 KB Output is correct
2 Correct 127 ms 4148 KB Output is correct
3 Correct 126 ms 4200 KB Output is correct
4 Correct 128 ms 4172 KB Output is correct
5 Correct 136 ms 4212 KB Output is correct
6 Correct 127 ms 4236 KB Output is correct
7 Correct 134 ms 4172 KB Output is correct
8 Correct 132 ms 4228 KB Output is correct
9 Correct 133 ms 4288 KB Output is correct
10 Correct 130 ms 4188 KB Output is correct
11 Correct 130 ms 4220 KB Output is correct
12 Correct 126 ms 4208 KB Output is correct
13 Correct 130 ms 4188 KB Output is correct
14 Correct 129 ms 4216 KB Output is correct
15 Correct 129 ms 4184 KB Output is correct
16 Correct 26 ms 980 KB Output is correct
17 Correct 28 ms 1004 KB Output is correct
18 Correct 27 ms 1000 KB Output is correct
19 Correct 30 ms 984 KB Output is correct
20 Correct 29 ms 980 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 4240 KB Output is correct
2 Correct 127 ms 4148 KB Output is correct
3 Correct 126 ms 4200 KB Output is correct
4 Correct 128 ms 4172 KB Output is correct
5 Correct 136 ms 4212 KB Output is correct
6 Correct 127 ms 4236 KB Output is correct
7 Correct 134 ms 4172 KB Output is correct
8 Correct 132 ms 4228 KB Output is correct
9 Correct 133 ms 4288 KB Output is correct
10 Correct 130 ms 4188 KB Output is correct
11 Correct 130 ms 4220 KB Output is correct
12 Correct 126 ms 4208 KB Output is correct
13 Correct 130 ms 4188 KB Output is correct
14 Correct 129 ms 4216 KB Output is correct
15 Correct 129 ms 4184 KB Output is correct
16 Correct 26 ms 980 KB Output is correct
17 Correct 28 ms 1004 KB Output is correct
18 Correct 27 ms 1000 KB Output is correct
19 Correct 30 ms 984 KB Output is correct
20 Correct 29 ms 980 KB Output is correct
21 Incorrect 872 ms 3880 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 4240 KB Output is correct
2 Correct 127 ms 4148 KB Output is correct
3 Correct 126 ms 4200 KB Output is correct
4 Correct 128 ms 4172 KB Output is correct
5 Correct 136 ms 4212 KB Output is correct
6 Correct 127 ms 4236 KB Output is correct
7 Correct 134 ms 4172 KB Output is correct
8 Correct 132 ms 4228 KB Output is correct
9 Correct 133 ms 4288 KB Output is correct
10 Correct 130 ms 4188 KB Output is correct
11 Correct 130 ms 4220 KB Output is correct
12 Correct 126 ms 4208 KB Output is correct
13 Correct 130 ms 4188 KB Output is correct
14 Correct 129 ms 4216 KB Output is correct
15 Correct 129 ms 4184 KB Output is correct
16 Correct 26 ms 980 KB Output is correct
17 Correct 28 ms 1004 KB Output is correct
18 Correct 27 ms 1000 KB Output is correct
19 Correct 30 ms 984 KB Output is correct
20 Correct 29 ms 980 KB Output is correct
21 Incorrect 872 ms 3880 KB Output isn't correct
22 Halted 0 ms 0 KB -