Submission #551919

#	Time	Username	Problem	Language	Result	Execution time	Memory
551919		nafis_shifat	Boat (APIO16_boat)	C++17	100 / 100	1454 ms	36028 KiB

boat

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1500+5;
const int inf=1e9;
const ll mod = 1e9 + 7;
ll bigmod(ll a, ll b) {
	if(b == 0) return 1;
	int mid = b / 2;

	ll res = bigmod(a, mid);
	res = res * res % mod;
	if(b % 2 == 1) return a * res % mod;
	return res;
}

ll last[mxn][mxn] = {};
ll dp[mxn][mxn] = {};
ll sum[mxn][mxn] = {};

ll fact[mxn], inv[mxn];

ll pre[mxn][mxn] = {};

ll ncr(ll n, ll r) {
	if(r > n) return 0;
	ll res = fact[n];
	res = res * inv[r] % mod;
	res = res * inv[n - r] % mod;
	return res;
}
int main() {
	fact[0] = 1;
	inv[0] = 1;

	for(int i = 1; i < mxn; i++) {
		fact[i] = fact[i - 1] * i % mod;
		inv[i] = bigmod(fact[i], mod - 2) % mod;
	}

	int n;
	cin >> n;
	int a[n + 1], b[n + 1];
	int l[n + 1] = {}, r[n + 1] = {};
	vector<int> v;
	v.push_back(0);
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		v.push_back(a[i]);
		v.push_back(a[i] - 1);
		v.push_back(b[i]);

	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	int len[v.size() + 2];
	for(int i = 1; i < v.size(); i++) len[i] = v[i] - v[i - 1];


	for(int i = 1; i < v.size(); i++) {
		
		for(int j = 1; j <= n; j++) {
			ll mul = 1;
			ll tot = 0;
			ll mul2 = 1;

			for(int k = 1; k <= min(j + 1, len[i]); k++) {

				mul = mul * (len[i] - k + 1) % mod;
				ll v1 = mul * inv[k] % mod;

				ll v2 = mul2 * inv[k - 1] % mod;

				// cout<<i<<" "<<j<<" "<<k<<endl;
				// assert(ncr(j - 1, k - 1) == v2);
				pre[i][j] += v2 * v1 % mod;

				mul2 = mul2 * (j - k) % mod;


			}


			pre[i][j] %= mod;
		}
	}



	for(int i = 1; i <= n; i++) {
		l[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		r[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
	}

	dp[0][0] = 1;
	for(int i = 0; i < v.size(); i++) sum[i][0] = 1;

	ll ans = 0;

    for(int p = 1; p <= n; p++) {
    	for(int i = l[p]; i <= r[p]; i++) {
    		ll tot = len[i];
    		ll found = 1;

    		for(int j = p - 1; j >= 0; j--) {


    			dp[i][j] = sum[i - 1][j] * pre[i][found] % mod;
    			sum[i][p] = (sum[i][p] + dp[i][j]) % mod;

    			if(l[j] <= i && i <= r[j]) found++;




    		}
    	}

    	for(int i = l[p]; i < v.size(); i++) sum[i][p] = (sum[i][p] + sum[i - 1][p]) % mod;

    	ans += sum[v.size() - 1][p];

  

    }



    cout<<ans % mod<<endl;


	
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 1; i < v.size(); i++) len[i] = v[i] - v[i - 1];
      |                 ~~^~~~~~~~~~
boat.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
boat.cpp:66:7: warning: unused variable 'tot' [-Wunused-variable]
   66 |    ll tot = 0;
      |       ^~~
boat.cpp:98:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for(int i = 0; i < v.size(); i++) sum[i][0] = 1;
      |                 ~~^~~~~~~~~~
boat.cpp:104:10: warning: unused variable 'tot' [-Wunused-variable]
  104 |       ll tot = len[i];
      |          ^~~
boat.cpp:121:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |      for(int i = l[p]; i < v.size(); i++) sum[i][p] = (sum[i][p] + sum[i - 1][p]) % mod;
      |                        ~~^~~~~~~~~~

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