제출 #733037

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

boat

#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 = 1005;

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){
		ans = (ans * base) % mod;
		base = (base * base) % mod;
		pw >>= 1;
	}
	return ans;
}

int 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 pref[N][N];

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());
	for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
	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();
	}
	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;
					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 'long long int pre(long long int, long long int)':
boat.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
   52 | }
      | ^
boat.cpp: In function 'void process()':
boat.cpp:64: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]
   64 |  for(int i = 1; i < vc.size(); i++) pre(vc[i] - vc[i - 1], i);
      |                 ~~^~~~~~~~~~~
boat.cpp:71: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]
   71 |  for(int j = 1; j < vc.size(); j++) dp[0][j] = pref[0][j] = 1;
      |                 ~~^~~~~~~~~~~
boat.cpp:74: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]
   74 |   for(int j = 1; j < vc.size(); j++){
      |                  ~~^~~~~~~~~~~
boat.cpp:93: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]
   93 |   for(int j = 1; j < vc.size(); j++){
      |                  ~~^~~~~~~~~~~

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