Submission #710557

#	Time	Username	Problem	Language	Result	Execution time	Memory
710557		lukameladze	Boat (APIO16_boat)	C++14	100 / 100	1344 ms	27064 KiB

boat

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 1005, mod = 1e9 + 7;
int t,n,a[N],b[N],pr[N][N],dp[N][N],inv[N],fq[N],ch[N][N],chh[N][N],sum[N][N];
map <int, int> shes;
vector <int> v;
int f_p(int base, int power) {
	int result = 1;
	while (power > 0) {
		if (power % 2) result = (result * base) % mod;
		base = (base * base) % mod;
		power /= 2;
	}
	return result;
}
int C(int n, int k) {
	if (n < k) return 0;
	if (n == 0 && k == 0) return 1;
	int pas = 1;
	for (int i = n; i >= n - k + 1; i--){
		pas *= i;
		pas %= mod;
	} 
	pas *= inv[k];pas %= mod;
	return pas;
}
int check(int le, int ri, int a, int b) {
	return (max(a,le) <= min(b,ri));
}
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
    	cin>>a[i]>>b[i];
    	v.pb(a[i]);
    	v.pb(b[i] + 1);
	}
	fq[0] = 1; inv[0] = 1;
	for (int i = 1; i < N; i++) {
		fq[i] = fq[i - 1] * i % mod;
	}
	inv[N - 1] = f_p(fq[N - 1], mod - 2);
	for (int i = N - 2; i >= 1; i--) {
		inv[i] = (inv[i + 1] * (i + 1)) % mod;
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());
	
	vector <pii> seg;
	vector <int> szz;
	seg.pb({-1,-1});
	for (int i = 1; i < v.size(); i++) {
		seg.pb({v[i - 1], v[i] - 1}); 
		szz.pb(v[i] - v[i - 1]);
	}
	sort(szz.begin(), szz.end());
	szz.resize(unique(szz.begin(), szz.end())-szz.begin());
	dp[0][0] = 1;
	pr[0][0] = 1; 
	ch[0][0] = 1;
	ch[1][1] = ch[1][0] = 1;
	for (int i = 2; i <= n; i++) {
	    ch[i][0] = 1;
	    for (int j = 1; j <= i; j++) {
	        ch[i][j] = (ch[i - 1][j] + ch[i - 1][j - 1]) % mod;
	    }
	}
	int raod = 0;
	for (int sz : szz) { raod++; shes[sz] = raod;
	    for (int cnt = 1; cnt <= n; cnt++) {
	        chh[raod][cnt] = C(sz, cnt);
	        for (int cn = 1; cn <= cnt; cn++) {
	            sum[raod][cnt] += chh[raod][cn] * ch[cnt - 1][cn - 1] % mod;
	            if (sum[raod][cnt] >= mod) sum[raod][cnt] -= mod;
	        }
	    }
	}
 
	int ans = 0;
	for (int i = 1; i < seg.size(); i++) pr[0][i] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < seg.size(); j++) {
			int le = seg[j].f; int ri = seg[j].s;
			if (check(le,ri,a[i],b[i])) { 
				int cnt = 1;
				int sh = shes[ri - le + 1];
				for (int prless = i - 1; prless >= 0; prless--) {
				    dp[i][j] += sum[sh][cnt] * pr[prless][j - 1] % mod;
				    //cout<<i<<" "<<j<<" "<<ri - le + 1<<" "<<cnt<<" "<<sum[ri - le + 1][cnt]<<"  "<<pr[prless][j - 1]<<endl;
				    if (dp[i][j] >= mod) dp[i][j] -= mod;
					if ((check(le,ri,a[prless],b[prless]))) cnt++;
				}
			}
			ans += dp[i][j]; if (ans >= mod) ans -= mod;
			pr[i][j] = (dp[i][j] + pr[i][j - 1]);  if (pr[i][j] >= mod) pr[i][j] -= mod;
		}
	}
	cout<<ans<<"\n";
}

Compilation message (stderr)

boat.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:57: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]
   57 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
boat.cpp:85:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 1; i < seg.size(); i++) pr[0][i] = 1;
      |                  ~~^~~~~~~~~~~~
boat.cpp:87:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for (int j = 1; j < seg.size(); j++) {
      |                   ~~^~~~~~~~~~~~

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