Submission #469992

#	Time	Username	Problem	Language	Result	Execution time	Memory
469992		ymm	Boat (APIO16_boat)	C++17	0 / 100	153 ms	4292 KiB

boat

///
///   ♪ Pizza mozzarella rella rella rella... ♪
///

#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef          long long   ll;
typedef unsigned long long  ull;
typedef std::pair<int,int>  pii;
typedef std::pair<ll ,ll >  pll;
using namespace std;

const int mod = 1e9 + 7;
const int N = 512;
vector<int> cmp;
int l[N], r[N];
int n;

ll dp[N][2*N];
ll fct[2*N], fci[2*N];
ll inv[2*N];
ll Inv(ll x){
    ll ans = 1;
    for(ll y = mod-2; y; y >>= 1){
        if(y&1) ans = ans*x % mod;
        x = x*x % mod;
    }
    return ans;
}

int main()
{
    FAST;
    cin >> n;
    inv[0] = fci[0] = fct[0] = 1;
    Loop(i,1,2*N) fct[i] = fct[i-1]*i % mod, fci[i] = Inv(fct[i]), inv[i] = Inv(i);
    Loop(i,0,n)
    {
        cin >> l[i] >> r[i];
        ++r[i];
        cmp.push_back(l[i]);
        cmp.push_back(r[i]);
    }
    cmp.push_back(1e9+10);
    sort(all(cmp)); cmp.resize(unique(all(cmp))-cmp.begin());
    Loop(i,0,2*N) dp[0][i] = 1;

    Loop(i,0,n)
    {
        Loop(j,0,cmp.size()-1)
        {
            ll m = cmp[j+1] - cmp[j];
            ll X = 1;
            int k = 0;
            LoopR(p,0,i+1)
            {
                if(r[i] <= cmp[j] || cmp[j+1] <= l[i]) continue;
                X = X*(m+k) % mod;
                X = X*inv[k+1] % mod;
                ++k;
                dp[i+1][j] = (dp[i+1][j] + X*dp[p][j]) % mod;
            }
        }

        ll sum = 1;
        Loop(j,0,cmp.size())
            sum += dp[i+1][j],
            dp[i+1][j] = sum - dp[i+1][j];
    }

    //Loop(i,0,n+1) {Loop(j,0,cmp.size()) cout << dp[i][j] << ' '; cout << '\n';}
    cout << (dp[n][cmp.size()-1]+mod-1)%mod << '\n';
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define Loop(x, l, r) for(int x = (l); x < (r); ++x)
      |                                          ^
boat.cpp:58:9: note: in expansion of macro 'Loop'
   58 |         Loop(j,0,cmp.size()-1)
      |         ^~~~
boat.cpp:8:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define Loop(x, l, r) for(int x = (l); x < (r); ++x)
      |                                          ^
boat.cpp:74:9: note: in expansion of macro 'Loop'
   74 |         Loop(j,0,cmp.size())
      |         ^~~~

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