제출 #480659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480659		TAMREF	Boat (APIO16_boat)	C++17	36 / 100	2078 ms	4316 KiB

boat

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct mint {
    static const int mod = 1e9 + 7;
    int v;
    mint(ll v = 0) : v(v % mod) {}
    mint operator+ (mint o) {
        return mint(v + o.v);
    }
    mint operator- (mint o) {
        return mint(v + mod - o.v);
    }
    mint operator* (mint o) {
        return mint(ll(v) * o.v);
    }
    mint operator^ (int n) {
        mint ret(1), pv(v);
        for(;n;n>>=1) {
            if(n & 1) ret = ret * pv;
            pv = pv * pv;
        }
        return ret;
    }
    mint inv() {
        return mint(v) ^ (mod - 2);
    }
    mint operator/ (mint o) {
        return mint(v) * o.inv();
    }
};

mint& operator+= (mint &a, mint b) {
    return a = a + b;
}

mint& operator-= (mint &a, mint b) {
    return a = a - b;
}

int n;
vector<int> cmp;
int a[505], b[505];

mint a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k
mint b_ij[2][1005]; //i' < i, j' < j, k' arb
mint ans;

int main(){
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ++b[i];
        cmp.pp(a[i]); cmp.pp(b[i]);
    }
    sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
    int d = szz(cmp);
    for(int i = 1; i <= n; i++) {
        a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
        b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < d; j++) {
            b_ij[i & 1][j] = b_ij[~i & 1][j] + b_ij[i & 1][j-1] - b_ij[~i & 1][j-1];
            for(int k = 1; k <= n; k++) {
                a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k];
                mint dp;
                if(a[i] <= j && j < b[i]) {
                    mint len = cmp[j] - cmp[j-1];
                    if(k == 1) {
                        dp = (mint(1) + b_ij[~i & 1][j-1]) * len;
                    }else{
                        dp = a_Ijk[~i & 1][j][k-1] * (len - mint(k - 1)) / mint(k);
                    }
                }
                a_Ijk[i & 1][j][k] += dp;
                b_ij[i & 1][j] += dp;
                ans += dp;
            }
        }
    }
    cout << (ans).v << endl;
}

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