oj.uz

Submission #1106255

# Submission time Handle Problem Language Result Execution time Memory
1106255 2024-10-29T16:39:52 Z _rain_ Boat (APIO16_boat) C++14
9 / 100
 540 ms 5940 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll ;
typedef pair<int,int> ii;
#define fi first
#define se second
#define name "main"
 
const int N=(int)500;
const int MOD=(int)1e9+7;
	int add(int a,int b){
		return a+b>=MOD?a+b-MOD:a+b;
	}
	int sub(int a,int b){
		return a-b<0?a-b+MOD:a-b;
	}
	int mul(int a,int b){
		return (ll)a*b%MOD;
	}
	int power(int a,int b){
		int res=1;
		for(;b;b>>=1,a=mul(a,a))
			if (b&1) res=mul(res,a);
		return res;
	}
vector<int>nen;
vector<ii>line;
int a[N+2],b[N+2],n;
int L[N+2]={},R[N+2]={},f[N*3+2][N+2]={},dp[N+2][N*3+2]={};
int sing[N+2]={},fact[N+2]={},inv[N+2]={},w[N+2]={};
int Combine(int x,int y){
	if (x>y) return 0;
	return (ll)fact[y]*inv[y-x]%MOD*inv[x]%MOD;
}

int C(int k,int n){
	if (k>n) return 0;
	int res=1;
	for(int i=n-k+1;i<=n;++i) res=mul(res,i);
	return mul(res,inv[k]);
}
bool intersec(ii x,int a,int b){
	if (b<x.fi||a>x.se) return false;
	return true;
}
 
void build(){
	memset(L,0x3f,sizeof L);
	memset(R,-0x3f,sizeof R);
	fact[0]=1;
	for(int i=1;i<=N;++i) fact[i]=mul(fact[i-1],i);
	inv[N]=power(fact[N],MOD-2);
	for(int i=N;i>=1;--i) inv[i-1]=mul(inv[i],i);
	for(int id=1;id<=line.size();++id){
		int dodai=line[id-1].se-line[id-1].fi+1;
		w[1]=dodai;
		for(int j=2;j<=min(dodai,n);++j) w[j]=mul(w[j-1],mul(inv[j],dodai-j+1));
		for(int j=1;j<=n;++j){
			for(int c=1;c<=min(j,dodai);++c)
				f[id][j]=add(f[id][j],mul(Combine(c-1,j-1),w[c]));
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=line.size();++j){
			if (intersec(line[j-1],a[i],b[i])) 
				L[i]=min(L[i],j),R[i]=max(R[i],j);
		}
	}
	return;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		nen.push_back(a[i]);
		nen.push_back(b[i]);
		nen.push_back(a[i]-1);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<nen.size();++i){
		if (i-1==0) line.push_back({nen[i-1],nen[i]});
		else line.push_back({nen[i-1]+1,nen[i]});
	}
	// cout<<nen.size()<<'\n';
	build();
	for(int i=0;i<=line.size();++i) dp[0][i]=1;
	for(int i=1;i<=n;++i){
		// cout<<i<<'\n';
		for(int id=L[i];id<=R[i];++id){
			int cnt=0;
			pair<int,int> xx=line[id-1];
			if (id==L[i]){
				int dodai=line[id-1].se-a[i]+1;
				for(int j=0;j<=i;++j) sing[j]=0;
				for(int j=1;j<=i;++j) w[j]=C(j,dodai);
				for(int j=1;j<=i;++j){
					for(int c=1;c<=j;++c)
						sing[j]=add(sing[j],mul(Combine(c-1,j-1),w[c]));
				}
				xx={a[i],line[id-1].se};
			}
			for(int j=i;j>=1;--j){
				if (intersec(xx,a[j],b[j])) ++cnt;
				if (id==L[i]) dp[i][id]=add(dp[i][id],mul(sing[cnt],dp[j-1][id-1]));
				else dp[i][id]=add(dp[i][id],mul(f[id][cnt],dp[j-1][id-1]));
			}
		}
		for(int j=L[i];j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=add(ans,dp[i][line.size()]);
	cout<<ans;
	exit(0);
}

Compilation message

boat.cpp: In function 'void build()':
boat.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int id=1;id<=line.size();++id){
      |               ~~^~~~~~~~~~~~~
boat.cpp:65:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int j=1;j<=line.size();++j){
      |               ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=1;i<nen.size();++i){
      |              ~^~~~~~~~~~~
boat.cpp:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=0;i<=line.size();++i) dp[0][i]=1;
      |              ~^~~~~~~~~~~~~
boat.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for(int j=L[i];j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
      |                  ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 4940 KB Output is correct
2 Correct 520 ms 4936 KB Output is correct
3 Correct 526 ms 4948 KB Output is correct
4 Correct 540 ms 4936 KB Output is correct
5 Correct 521 ms 4972 KB Output is correct
6 Correct 522 ms 4936 KB Output is correct
7 Correct 515 ms 4936 KB Output is correct
8 Correct 519 ms 4936 KB Output is correct
9 Correct 516 ms 5108 KB Output is correct
10 Correct 518 ms 4992 KB Output is correct
11 Correct 528 ms 4936 KB Output is correct
12 Correct 524 ms 4936 KB Output is correct
13 Correct 516 ms 4936 KB Output is correct
14 Correct 528 ms 4956 KB Output is correct
15 Correct 533 ms 5184 KB Output is correct
16 Correct 187 ms 2888 KB Output is correct
17 Correct 192 ms 2904 KB Output is correct
18 Correct 207 ms 2888 KB Output is correct
19 Correct 195 ms 3092 KB Output is correct
20 Correct 195 ms 2888 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 4940 KB Output is correct
2 Correct 520 ms 4936 KB Output is correct
3 Correct 526 ms 4948 KB Output is correct
4 Correct 540 ms 4936 KB Output is correct
5 Correct 521 ms 4972 KB Output is correct
6 Correct 522 ms 4936 KB Output is correct
7 Correct 515 ms 4936 KB Output is correct
8 Correct 519 ms 4936 KB Output is correct
9 Correct 516 ms 5108 KB Output is correct
10 Correct 518 ms 4992 KB Output is correct
11 Correct 528 ms 4936 KB Output is correct
12 Correct 524 ms 4936 KB Output is correct
13 Correct 516 ms 4936 KB Output is correct
14 Correct 528 ms 4956 KB Output is correct
15 Correct 533 ms 5184 KB Output is correct
16 Correct 187 ms 2888 KB Output is correct
17 Correct 192 ms 2904 KB Output is correct
18 Correct 207 ms 2888 KB Output is correct
19 Correct 195 ms 3092 KB Output is correct
20 Correct 195 ms 2888 KB Output is correct
21 Incorrect 355 ms 5940 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 4940 KB Output is correct
2 Correct 520 ms 4936 KB Output is correct
3 Correct 526 ms 4948 KB Output is correct
4 Correct 540 ms 4936 KB Output is correct
5 Correct 521 ms 4972 KB Output is correct
6 Correct 522 ms 4936 KB Output is correct
7 Correct 515 ms 4936 KB Output is correct
8 Correct 519 ms 4936 KB Output is correct
9 Correct 516 ms 5108 KB Output is correct
10 Correct 518 ms 4992 KB Output is correct
11 Correct 528 ms 4936 KB Output is correct
12 Correct 524 ms 4936 KB Output is correct
13 Correct 516 ms 4936 KB Output is correct
14 Correct 528 ms 4956 KB Output is correct
15 Correct 533 ms 5184 KB Output is correct
16 Correct 187 ms 2888 KB Output is correct
17 Correct 192 ms 2904 KB Output is correct
18 Correct 207 ms 2888 KB Output is correct
19 Correct 195 ms 3092 KB Output is correct
20 Correct 195 ms 2888 KB Output is correct
21 Incorrect 355 ms 5940 KB Output isn't correct
22 Halted 0 ms 0 KB -