oj.uz

Submission #1106247

# Submission time Handle Problem Language Result Execution time Memory
1106247 2024-10-29T16:23:24 Z _rain_ Boat (APIO16_boat) C++14
36 / 100
 1404 ms 12632 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)1000;
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+2][2*N+2]={},dp[N+2][2*N+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<=n;++j) w[j]=C(j,dodai);
		for(int j=1;j<=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);

	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]});
	}
	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<=n;++j) sing[j]=0;
				for(int j=1;j<=n;++j) w[j]=C(j,dodai);
				for(int j=1;j<=n;++j){
					for(int c=1;c<=j;++c)
						sing[j]=add(sing[j],mul(Combine(c-1,j),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=1;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: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:90: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]
   90 |  for(int i=0;i<=line.size();++i) dp[0][i]=1;
      |              ~^~~~~~~~~~~~~
boat.cpp:112: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]
  112 |   for(int j=1;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 1365 ms 10312 KB Output is correct
2 Correct 1404 ms 10312 KB Output is correct
3 Correct 1366 ms 10412 KB Output is correct
4 Correct 1374 ms 10332 KB Output is correct
5 Correct 1363 ms 10392 KB Output is correct
6 Correct 1372 ms 10336 KB Output is correct
7 Correct 1358 ms 10312 KB Output is correct
8 Correct 1404 ms 10312 KB Output is correct
9 Correct 1389 ms 10312 KB Output is correct
10 Correct 1389 ms 10312 KB Output is correct
11 Correct 1376 ms 10272 KB Output is correct
12 Correct 1388 ms 10312 KB Output is correct
13 Correct 1352 ms 10336 KB Output is correct
14 Correct 1389 ms 10376 KB Output is correct
15 Correct 1364 ms 10328 KB Output is correct
16 Correct 545 ms 3912 KB Output is correct
17 Correct 554 ms 3792 KB Output is correct
18 Correct 550 ms 3704 KB Output is correct
19 Correct 552 ms 3832 KB Output is correct
20 Correct 544 ms 3964 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 10312 KB Output is correct
2 Correct 1404 ms 10312 KB Output is correct
3 Correct 1366 ms 10412 KB Output is correct
4 Correct 1374 ms 10332 KB Output is correct
5 Correct 1363 ms 10392 KB Output is correct
6 Correct 1372 ms 10336 KB Output is correct
7 Correct 1358 ms 10312 KB Output is correct
8 Correct 1404 ms 10312 KB Output is correct
9 Correct 1389 ms 10312 KB Output is correct
10 Correct 1389 ms 10312 KB Output is correct
11 Correct 1376 ms 10272 KB Output is correct
12 Correct 1388 ms 10312 KB Output is correct
13 Correct 1352 ms 10336 KB Output is correct
14 Correct 1389 ms 10376 KB Output is correct
15 Correct 1364 ms 10328 KB Output is correct
16 Correct 545 ms 3912 KB Output is correct
17 Correct 554 ms 3792 KB Output is correct
18 Correct 550 ms 3704 KB Output is correct
19 Correct 552 ms 3832 KB Output is correct
20 Correct 544 ms 3964 KB Output is correct
21 Runtime error 717 ms 12632 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2128 KB Output is correct
2 Correct 19 ms 2128 KB Output is correct
3 Correct 21 ms 2220 KB Output is correct
4 Correct 22 ms 2128 KB Output is correct
5 Correct 21 ms 2296 KB Output is correct
6 Correct 20 ms 2216 KB Output is correct
7 Correct 20 ms 2128 KB Output is correct
8 Correct 22 ms 2128 KB Output is correct
9 Correct 24 ms 2128 KB Output is correct
10 Correct 21 ms 2320 KB Output is correct
11 Correct 19 ms 2128 KB Output is correct
12 Correct 19 ms 2128 KB Output is correct
13 Correct 19 ms 2172 KB Output is correct
14 Correct 22 ms 2128 KB Output is correct
15 Correct 20 ms 2128 KB Output is correct
16 Correct 11 ms 1360 KB Output is correct
17 Correct 11 ms 1360 KB Output is correct
18 Correct 11 ms 1616 KB Output is correct
19 Correct 11 ms 1628 KB Output is correct
20 Correct 11 ms 1360 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1365 ms 10312 KB Output is correct
2 Correct 1404 ms 10312 KB Output is correct
3 Correct 1366 ms 10412 KB Output is correct
4 Correct 1374 ms 10332 KB Output is correct
5 Correct 1363 ms 10392 KB Output is correct
6 Correct 1372 ms 10336 KB Output is correct
7 Correct 1358 ms 10312 KB Output is correct
8 Correct 1404 ms 10312 KB Output is correct
9 Correct 1389 ms 10312 KB Output is correct
10 Correct 1389 ms 10312 KB Output is correct
11 Correct 1376 ms 10272 KB Output is correct
12 Correct 1388 ms 10312 KB Output is correct
13 Correct 1352 ms 10336 KB Output is correct
14 Correct 1389 ms 10376 KB Output is correct
15 Correct 1364 ms 10328 KB Output is correct
16 Correct 545 ms 3912 KB Output is correct
17 Correct 554 ms 3792 KB Output is correct
18 Correct 550 ms 3704 KB Output is correct
19 Correct 552 ms 3832 KB Output is correct
20 Correct 544 ms 3964 KB Output is correct
21 Runtime error 717 ms 12632 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -