oj.uz

Submission #1106251

# Submission time Handle Problem Language Result Execution time Memory
1106251 2024-10-29T16:34:52 Z _rain_ Boat (APIO16_boat) C++14
9 / 100
 768 ms 5812 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;
		for(int j=1;j<=min(dodai,n);++j) w[j]=C(j,dodai);
		for(int j=1;j<=min(dodai+1,n);++j){
			for(int c=1;c<=j;++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);
	// freopen(name".inp","r",stdin);
	// freopen(name".out","w",stdout);
	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:64: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]
   64 |   for(int j=1;j<=line.size();++j){
      |               ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i=1;i<nen.size();++i){
      |              ~^~~~~~~~~~~
boat.cpp:92: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]
   92 |  for(int i=0;i<=line.size();++i) dp[0][i]=1;
      |              ~^~~~~~~~~~~~~
boat.cpp:114: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]
  114 |   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 765 ms 4952 KB Output is correct
2 Correct 763 ms 5148 KB Output is correct
3 Correct 763 ms 5132 KB Output is correct
4 Correct 763 ms 4936 KB Output is correct
5 Correct 768 ms 4956 KB Output is correct
6 Correct 765 ms 5192 KB Output is correct
7 Correct 764 ms 5160 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 763 ms 5144 KB Output is correct
10 Correct 768 ms 4936 KB Output is correct
11 Correct 765 ms 4932 KB Output is correct
12 Correct 763 ms 5084 KB Output is correct
13 Correct 763 ms 5080 KB Output is correct
14 Correct 763 ms 5056 KB Output is correct
15 Correct 764 ms 4960 KB Output is correct
16 Correct 229 ms 2884 KB Output is correct
17 Correct 241 ms 2888 KB Output is correct
18 Correct 233 ms 2912 KB Output is correct
19 Correct 238 ms 2884 KB Output is correct
20 Correct 242 ms 2888 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 4952 KB Output is correct
2 Correct 763 ms 5148 KB Output is correct
3 Correct 763 ms 5132 KB Output is correct
4 Correct 763 ms 4936 KB Output is correct
5 Correct 768 ms 4956 KB Output is correct
6 Correct 765 ms 5192 KB Output is correct
7 Correct 764 ms 5160 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 763 ms 5144 KB Output is correct
10 Correct 768 ms 4936 KB Output is correct
11 Correct 765 ms 4932 KB Output is correct
12 Correct 763 ms 5084 KB Output is correct
13 Correct 763 ms 5080 KB Output is correct
14 Correct 763 ms 5056 KB Output is correct
15 Correct 764 ms 4960 KB Output is correct
16 Correct 229 ms 2884 KB Output is correct
17 Correct 241 ms 2888 KB Output is correct
18 Correct 233 ms 2912 KB Output is correct
19 Correct 238 ms 2884 KB Output is correct
20 Correct 242 ms 2888 KB Output is correct
21 Incorrect 335 ms 5812 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 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 765 ms 4952 KB Output is correct
2 Correct 763 ms 5148 KB Output is correct
3 Correct 763 ms 5132 KB Output is correct
4 Correct 763 ms 4936 KB Output is correct
5 Correct 768 ms 4956 KB Output is correct
6 Correct 765 ms 5192 KB Output is correct
7 Correct 764 ms 5160 KB Output is correct
8 Correct 766 ms 4936 KB Output is correct
9 Correct 763 ms 5144 KB Output is correct
10 Correct 768 ms 4936 KB Output is correct
11 Correct 765 ms 4932 KB Output is correct
12 Correct 763 ms 5084 KB Output is correct
13 Correct 763 ms 5080 KB Output is correct
14 Correct 763 ms 5056 KB Output is correct
15 Correct 764 ms 4960 KB Output is correct
16 Correct 229 ms 2884 KB Output is correct
17 Correct 241 ms 2888 KB Output is correct
18 Correct 233 ms 2912 KB Output is correct
19 Correct 238 ms 2884 KB Output is correct
20 Correct 242 ms 2888 KB Output is correct
21 Incorrect 335 ms 5812 KB Output isn't correct
22 Halted 0 ms 0 KB -