oj.uz

답안 #1106058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106058 2024-10-29T05:36:34 Z _rain_ Boat (APIO16_boat) C++14
0 / 100
 306 ms 4304 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 inv[N+2]={};
int L[N+2]={},R[N+2]={},f[N+2][2*N+2]={},dp[N+2][2*N+2]={};

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);
	int tich=1;
	inv[0]=power(tich,MOD-2);
	for(int i=1;i<=N;++i) {
		tich=mul(tich,i);
		inv[i]=power(tich,MOD-2);
	}
	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){
			f[id][j]=add(f[id][j-1],C(j,dodai));
		}
	}
	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]);
	}
	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){
		for(int id=L[i];id<=R[i];++id){
			int cnt=0;
			for(int j=i;j>=1;--j){
				if (intersec(line[id-1],a[j],b[j])) ++cnt;
				dp[i][id]=add(dp[i][id],mul(f[id][cnt],dp[j-1][id-1]));
			}
		}
		for(int j=0;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i-1][j]);
		//for(int id=L[i];id<=R[i];++id) cout<<line[id-1].fi<<' '<<line[id-1].se<<'\n';
	}
	int ans=0;
	for(int i=0;i<line.size();++i) ans=add(ans,sub(dp[n][i],1));
	cout<<ans;
	exit(0);
}

Compilation message

boat.cpp: In function 'void build()':
boat.cpp:53: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]
   53 |  for(int id=1;id<=line.size();++id){
      |               ~~^~~~~~~~~~~~~
boat.cpp:60: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]
   60 |   for(int j=1;j<=line.size();++j){
      |               ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=1;i<nen.size();++i){
      |              ~^~~~~~~~~~~
boat.cpp:84: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]
   84 |  for(int i=0;i<=line.size();++i) dp[0][i]=1;
      |              ~^~~~~~~~~~~~~
boat.cpp:93: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]
   93 |   for(int j=0;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i-1][j]);
      |               ~^~~~~~~~~~~~~
boat.cpp:97: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]
   97 |  for(int i=0;i<line.size();++i) ans=add(ans,sub(dp[n][i],1));
      |              ~^~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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