Submission #1126169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126169		TrendBattles	Boat (APIO16_boat)	C++17	9 / 100	9 ms	4172 KiB

boat

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

#define INFILE "lis_regional.inp"
#define OUTFILE "lis_regional.out"


//Thank you GlowCheese
template <const int m> 
struct Mint {
    int v; static_assert(m > 0);
    Mint(lli value = 0): v(value % m) { if (v < 0) v += m; }
    friend istream& operator >> (istream& inp, Mint& a) {
        lli x; inp >> x;
        a = x; return inp;
    }
    friend ostream& operator << (ostream& out, const Mint& a) { out << a.v; return out; }
    
    Mint operator + () const { return *this; }
    Mint operator - () const { return Mint() - *this; }
    
    Mint& operator++() { ++v; if (v == m) v = 0; return *this; }
    Mint& operator--() { if (v == 0) v = m; --v; return *this; }
    Mint operator++(int) { Mint ans = *this; ++*this; return ans; }
    Mint operator--(int) { Mint ans = *this; --*this; return ans; }
    
    Mint& operator += (const Mint& other) { v += other.v; if (v >= m) v -= m; return *this; }
    Mint& operator -= (const Mint& other) { v -= other.v; if (v < 0) v += m; return *this; }
    Mint& operator *= (const Mint& other) { v = int64_t(v) * other.v % m; if (v < 0) v += m; return *this; }
    Mint inv() const {
        lli a = 1, b = 0;
        for (lli x = v, y = m; x != 0;)
            swap(a, b -= y / x * a), swap(x, y -= y / x * x);
        if (b < 0) b += m;
        return b;
    }
    Mint& operator /= (const Mint& other) { return *this *= other.inv(); }
    
    friend Mint operator + (const Mint& a, const Mint& b) { return Mint(a) += b; }
    friend Mint operator - (const Mint& a, const Mint& b) { return Mint(a) -= b; }
    friend Mint operator * (const Mint& a, const Mint& b) { return Mint(a) *= b; }
    friend Mint operator / (const Mint& a, const Mint& b) { return Mint(a) /= b; }
    
    friend bool operator == (const Mint& a, const Mint& b) { return a.v == b.v; }
    friend bool operator != (const Mint& a, const Mint& b) { return a.v != b.v; }
};

const int mod = (int) 1e9 + 7;
using mint = Mint <mod>;

const int MAX_N = 500;
mint pref[MAX_N][2 * MAX_N], dp[MAX_N][2 * MAX_N];
mint inv[MAX_N + 10];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    int N; cin >> N;
    vector <int> A(N), B(N);

    vector <int> points;
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        points.push_back(A[i]);
        points.push_back(B[i] + 1);
    }

    for (int i = 1; i <= N; ++i) {
        inv[i] = mint(1) / i;
    }

    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());

    const int M = (int) points.size();

    for (int i = 0; i < N; ++i) {
        for (int block = 0; block + 1 < M; ++block) {
            mint coeff = 1;

            for (int p = i; p >= 0; --p) {
                if (points[block + 1] <= A[p] or points[block] >= B[p] + 1) break;

                int len = i - p + 1;
                
                coeff *= (points[block + 1] - points[block] - len + 1) * inv[len];

                mint other = 1;
                if (p > 0 and block > 0) {
                    other += pref[p - 1][block - 1];
                }

                // if (debugging) {
                //     cerr << "POS: " << p << ' ' << other << ' ' << coeff << '\n';
                //     cerr << (points[block + 1] - points[block] - len + 1) << ' ' << inv[len] << '\n';
                // }

                dp[i][block] += other * coeff;
            }

            pref[i][block] += dp[i][block];
            if (block > 0) pref[i][block] += pref[i][block - 1];
        }

        if (i > 0) {
            for (int block = 0; block + 1 < M; ++block) {
                pref[i][block] += pref[i - 1][block];
            }
        }

        // cerr << "DEBUG " << i << '\n';
        // for (int block = 0; block + 1 < M; ++block) {
        //     cerr << points[block] << ' ' << points[block + 1] << ' ' << dp[i][block] << '\n';
        // }
    }

    cout << pref[N - 1][M - 2];
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
boat.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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