제출 #733051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
733051		minhcool	Boat (APIO16_boat)	C++17	100 / 100	827 ms	30300 KiB

boat

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi,sse,sse2,sse3,sse4")
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3005;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, a[N], b[N];
int dp[N][N];
 
vector<int> vc;
 
int le[N], ri[N];
 
int prep[N][N];
int inv[N];
 
int binpw(int base, int pw){
	int ans = 1;
	while(pw){
		if(pw & 1) ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}
 
void pre(int x, int ind){
	if(!inv[0]){
		inv[0] = 1;
		for(int i = 1; i <= n; i++){
			inv[i] = binpw(i, mod - 2) % mod;
		}
	}
	int ans = 1;
	prep[ind][0] = 1;
	for(int i = 1; i <= min(x, n); i++){
		ans = (ans * (x - i + 1)) % mod;
		ans = (ans * inv[i]) % mod;
		prep[ind][i] = ans;
	}
}
 
int c[N][N];
 
int pref[N][N];
 
int precal[N][N];
 
void pr(){
	c[0][0] = 1;
	for(int i = 1; i <= n; i++){
		c[i][0] = 1;
		for(int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}
	for(int j = 1; j < vc.size(); j++){
		for(int cnt = 2; cnt <= n; cnt++){
			for(int temp = 2; temp <= cnt; temp++){
				precal[j][cnt] = (precal[j][cnt] + c[cnt - 2][temp - 2] * prep[j][temp]) % mod;
			}
		}
	}
}
 
void process(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		a[i]--;
		vc.pb(a[i]), vc.pb(b[i]);
	}
	sort(vc.begin(), vc.end());
	vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
	for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
	pr();
	for(int i = 1; i <= n; i++){
		le[i] = lower_bound(vc.begin(), vc.end(), a[i]) - vc.begin();
		le[i]++;
		ri[i] = lower_bound(vc.begin(), vc.end(), b[i]) - vc.begin();
		//cout << i << " " << le[i] << " " << ri[i] << "\n";
	}
	dp[0][0] = pref[0][0] = 1;
	for(int j = 1; j < vc.size(); j++) dp[0][j] = pref[0][j] = 1;
	for(int i = 1; i <= n; i++){
		dp[i][0] = pref[i][0] = 1;
		for(int j = 1; j < vc.size(); j++){
			if(le[i] > j || ri[i] < j){
				//pref[i][j] = pref[i - 1][j];
				continue;
			}
			dp[i][j] = (pref[i - 1][j - 1] * prep[j][1]) % mod;
			//dp[i][j] = dp[i - 1][j];
			int sum = 0, cnt = 1;
			for(int k = i - 1; k >= 1; k--){
				//if(le[k] > j || ri[k] < j) break;
				if(le[k] <= j && ri[k] >= j){
					cnt++;
					//sum = (sum + pref[j][cnt]) % mod;
					int sum2 = 0;
					/*
					for(int temp = 2; temp <= cnt; temp++){
						sum2 = (sum2 + c[cnt - 2][temp - 2] * prep[j][temp]) % mod;
					}
					dp[i][j] = (dp[i][j] + pref[k - 1][j - 1] * sum2) % mod;*/
					dp[i][j] = (dp[i][j] + pref[k - 1][j - 1] * precal[j][cnt]) % mod;
					//dp[i][j] = (dp[i][j] + (pref[k - 1][j - 1] * sum)) % mod;
					//dp[i][j] += dp[i - 1][j - 1] * prep;
				}
			}
			//pref[i][j] += pref[i - 1][j];
		}
		for(int j = 1; j < vc.size(); j++){
			pref[i][j] = (pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + dp[i][j] + 3 * mod) % mod;
		}
	}
	for(int i = 0; i <= n; i++){
		//for(int j = 0; j < vc.size(); j++) cout << i << " " << j << " " << pref[i][j] << "\n";
	}
	cout << (pref[n][vc.size() - 1] + mod - 1) % mod << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
 

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'void pr()':
boat.cpp:69:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int j = 1; j < vc.size(); j++){
      |                 ~~^~~~~~~~~~~
boat.cpp: In function 'void process()':
boat.cpp:87:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
      |                 ~~^~~~~~~~~~~
boat.cpp:96:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int j = 1; j < vc.size(); j++) dp[0][j] = pref[0][j] = 1;
      |                 ~~^~~~~~~~~~~
boat.cpp:99:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = 1; j < vc.size(); j++){
      |                  ~~^~~~~~~~~~~
boat.cpp:112:10: warning: unused variable 'sum2' [-Wunused-variable]
  112 |      int sum2 = 0;
      |          ^~~~
boat.cpp:106:8: warning: unused variable 'sum' [-Wunused-variable]
  106 |    int sum = 0, cnt = 1;
      |        ^~~
boat.cpp:125:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for(int j = 1; j < vc.size(); j++){
      |                  ~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42