Submission #1126184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126184		TrendBattles	Boat (APIO16_boat)	C++17	100 / 100	536 ms	6440 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 dp[2][2 * MAX_N][MAX_N + 10];

mint choose_len[2 * MAX_N][MAX_N + 10];
mint pref[2 * MAX_N];

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);
    }

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

    const int M = (int) points.size();
    
    for (int block = 0; block + 1 < M; ++block) {
        int total_len = points[block + 1] - points[block];
        choose_len[block][0] = 1;
        
        for (int len = 1; len <= N; ++len) {
            choose_len[block][len] = choose_len[block][len - 1] * (total_len - len + 1) / len;
        }
    }

    for (int block = 0; block + 1 < M; ++block) {
        dp[0][block][1] = points[block] >= A[0] and points[block + 1] <= B[0] + 1;
    }   

    for (int i = 1; i < N; ++i) {
        memset(pref, 0, sizeof pref);

        int nxt = i & 1, prv = nxt ^ 1;
        memset(dp[nxt], 0, sizeof dp[nxt]);

        for (int block = 0; block + 1 < M; ++block) {
            for (int cons = 1; cons <= i; ++cons) {
                mint& now = dp[prv][block][cons];

                dp[nxt][block][cons] += now;
                if (points[block] >= A[i] and points[block + 1] <= B[i] + 1) {
                    dp[nxt][block][cons + 1] += now;
                }
                

                if (block + 2 < M) {
                    pref[block + 1] += now * choose_len[block][cons];
                }
            }
        }

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

            if (points[block] >= A[i] and points[block + 1] <= B[i] + 1) {
                dp[nxt][block][1] += pref[block] + 1;
            }
        }
    }

    mint ans = 0;

    for (int block = 0; block + 1 < M; ++block) {
        for (int cons = 1; cons <= N; ++cons) {
            ans += dp[(N - 1) & 1][block][cons] * choose_len[block][cons];
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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