Submission #363135

#	Time	Username	Problem	Language	Result	Execution time	Memory
363135		alireza_kaviani	Boat (APIO16_boat)	C++11	100 / 100	844 ms	8588 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)						(x).begin(),(x).end()
#define X							first
#define Y							second
#define sep							' '
#define endl						'\n'
#define SZ(x)						ll(x.size())

const ll MAXN = 1000 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , L[MAXN] , R[MAXN] , dp[MAXN][MAXN] , ps[MAXN] , inv[MAXN];
vector<int> compress = {0};

ll poww(ll a , ll b){
	ll ans = 1;
	for( ; b ; b /= 2 , a = a * a % MOD)	if(b & 1)	ans = ans * a % MOD;
	return ans;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	for(int i = 1 ; i < MAXN ; i++)	inv[i] = poww(i , MOD - 2);
//	for(int i = 1 ; i <= 5 ; i++)	cout << i << sep << inv[i] << endl;
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		cin >> L[i] >> R[i]; R[i]++;
		compress.push_back(L[i]);
		compress.push_back(R[i]);
	}
	sort(all(compress));
	compress.resize(unique(all(compress)) - compress.begin());
	dp[0][0] = 1; fill(ps , ps + MAXN , 1);
	for(int i = 1 ; i <= n ; i++){
		L[i] = lower_bound(all(compress) , L[i]) - compress.begin();
		R[i] = lower_bound(all(compress) , R[i]) - compress.begin();
		for(int j = L[i] ; j < R[i] ; j++){
			int len = compress[j + 1] - compress[j];
			for(int k = n ; k >= 2 ; k--){
				dp[j][k] = (dp[j][k] + dp[j][k - 1] * (len - k + 1) % MOD * inv[k]) % MOD;
			}
			dp[j][1] = (dp[j][1] + ps[j - 1] * len) % MOD;
		}
		ps[0] = dp[0][0];
		for(int j = 1 ; j < MAXN ; j++){
			ps[j] = ps[j - 1];
			for(int k = 0 ; k <= n ; k++){
				ps[j] = (ps[j] + dp[j][k]);
			}
			ps[j] %= MOD;
		}
	}
	cout << (ps[MAXN - 1] + MOD - 1) % MOD << endl;

    return 0;
}
/*

*/

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