Submission #795951

#	Time	Username	Problem	Language	Result	Execution time	Memory
795951		bane	Boat (APIO16_boat)	C++17	9 / 100	685 ms	10532 KiB

boat

#include<bits/stdc++.h>
    using namespace std;
     
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
     
    /*
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace __gnu_pbds;
    template <class T>
    using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    */
     
     
    #ifdef LOCAL
    #include "algo/debug.h"
    #else
    #define debug(...) 42
    #endif
     
    #define rep(i, n) for (int i = 0; i < (n); ++i)
    #define rep1(i, n) for (int i = 1; i < (n); ++i)
    #define rep1n(i, n) for (int i = 1; i <= (n); ++i)
    #define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
     
     
    #define fr first
    #define sc second
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define endl '\n'
     
     
    using ll = long long;
    using ull = unsigned long long;
    using ld = long double;
    using str = string;
    using pi = pair<int, int>;
    using pl = pair<ll, ll>;
     
    using vi = vector<int>;
    using vl = vector<ll>;
    using vpi = vector<pair<int, int>>;
    using vvi = vector<vi>;
     
    const int nax = (int)501;
    const int mod = (int)1e9 + 7;
     
    int a[nax], b[nax];
     
    ll bpow(ll a, ll b){
    	ll res = 1;
    	while(b){
    		if (b & 1)
    			res = (a * res) % mod;
    		b /= 2;
    		a = (a * a) % mod;
    	}
    	return res;
    }
     
     
    ll O = bpow(2,mod - 2);
     
    ll c (ll a){
    	return (((a * (a - 1))%mod) * O)%mod;
    }
     
    void solve(){
    	int n;
    	cin >> n;
    	vector<int>pts;	
    	rep1n(i,n){
    		cin >> a[i] >> b[i];
    		pts.pb(a[i]);
    		pts.pb(b[i]);
    		pts.pb(b[i] + 1);
    	}
    	pts.push_back(0);
    	sort(all(pts));
    	pts.erase(unique(all(pts)), pts.end());
    	int m = pts.size();
    	ll dp[n + 1][m + 1];
    	memset(dp, 0LL, sizeof(dp));
    	dp[0][0] = 1;
    	ll choose[m + 1][n + 1];
    	rep(i,m - 1){
    		choose[i][1] = pts[i + 1] - pts[i]; 
    		for(int j = 2; j <= n; j++){
    			choose[i][j] = (choose[i][j - 1] * bpow(j, mod - 2) % mod) * ((pts[i + 1] - pts[i] - j + 1 + mod)%mod) % mod;
    		}
    	}
    	ll orz[m + 1];
    	memset(orz, 0, sizeof(orz));
    	rep1n(i,n){
    		rep(j,m){
    			dp[i][j] = dp[i - 1][j];
    			//cout << dp[i][j] << " ";
    		}
    		rep(j,m - 1){
    			if (a[i] <= pts[j] && pts[j + 1] <= b[i] + 1){
    				//in range [L, R)
    				ll factor = 0;
    				orz[j]++;
					rep1n(p, orz[j]){
						factor += choose[j][p];
						factor %= mod;
					}
    				repr(k,j){
    					//dp[i-1][k]
    					dp[i][j] += dp[i - 1][k] * factor % mod;
    					dp[i][j] %= mod;
    				}
    			}
    		}
    	}
    	
    	ll ans = 0;
    	rep1n(i,m-2){
    		//cout << dp[n][i] << endl;
    		ans += dp[n][i];
    		ans %= mod;
    	}
    	cout << ans << '\n';
    }
     
    int main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);	
    	int tt = 1;
    	//cin >> tt;
    	while(tt--){
    		solve();
    	}
    	return 0;
    }

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