Submission #792897

#	Time	Username	Problem	Language	Result	Execution time	Memory
792897		Cookie	Boat (APIO16_boat)	C++14	100 / 100	460 ms	4428 KiB

boat

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e16;
const int mxn = 3e5 + 5;
int n;
ll l[505], r[505], inv[505], dp[1005][505];
ll pw(ll a, ll b){
    ll res = 1;
    for(;b;b >>= 1){
        if(b & 1){
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
    }
    return(res);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    vt<int>comp;
    for(int i = 1; i <= n; i++){
        cin >> l[i] >> r[i];
        inv[i] = pw(i, mod - 2);
        comp.pb(l[i]); comp.pb(r[i] + 1);
    }
    comp.pb(0);
    sort(comp.begin(), comp.end()); comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    for(int i = 0; i <= n; i++){
        dp[0][i] = 1;
    }
    for(int i = 1; i < sz(comp) - 1; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = dp[i - 1][j];
            ll ways = 1, cnt = 0;
            for(int k = j; k >= 1; k--){
                if(l[k] <= comp[i] && comp[i + 1] - 1 <= r[k]){
                    cnt++;
                    ll sus = ((comp[i + 1] - comp[i] + cnt - 1) * inv[cnt]) % mod;
                    ways = (ways * sus) % mod;
                    //cout << sus << " ";
                    dp[i][j] = (dp[i][j] + dp[i - 1][k - 1] * ways) % mod;
                }
            }
        }
    }
    cout << (dp[sz(comp) - 2][n] - 1 + mod) % mod;
    return(0);
}

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