제출 #679200

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679200		bebra	Boat (APIO16_boat)	C++17	9 / 100	2080 ms	11352 KiB

boat

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

#define dbg(x) cerr << #x << ": " << x << endl;


struct Seg {
    int l;
    int r;

    bool empty() const {
        return r - l + 1 <= 0;
    }

    friend Seg intersect(const Seg& lhs, const Seg& rhs) {
        return {max(lhs.l, rhs.l), min(lhs.r, rhs.r)};
    }
};


const int MOD = 1e9 + 7;
const int INV2 = 500000004;

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) res -= MOD;
    return res;
}

int mul(long long a, int b) {
    return a * b % MOD;
}

const int MAX_N = 500 + 1;
Seg segs[MAX_N];
int dp[MAX_N];

map<tuple<int, int, int>, int> mem;


int solve(int l, int r, int pos) {
    if (mem.find({l, r, pos}) != mem.end()) {
        return mem.at({l, r, pos});
    }
    if (r - l + 1 <= 0) {
        return 0;
    }
    int res = 0;
    for (int i = pos; i >= 0; --i) {
        if (r < segs[i].l) {
            continue;
        }
        if (l > segs[i].r) {
            res = add(res, mul(dp[i], r - l + 1));
            continue;
        }
        auto [l1, r1] = intersect(Seg{l, r}, segs[i]);
        res = add(res, mul(r - r1, dp[i]));
        res = add(res, mul(solve(l1, r1, i - 1), mul(r1 - l1, INV2)));
        res = add(res, mul(solve(segs[i].l, l1 - 1, i - 1), r1 - l + 1));
    }
    mem[{l, r, pos}] = res;
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> segs[i].l >> segs[i].r;
    }
    segs[0] = {-1, -1};
    dp[0] = 1;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = solve(segs[i].l, segs[i].r, i - 1);
        ans = add(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}


/*
2
3 4
1 6

*/

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