Submission #1281135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281135		jioung	Boat (APIO16_boat)	C++20	9 / 100	330 ms	12360 KiB

boat

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

#define io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define eb emplace_back
#define endl '\n'
#define int long long

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;

const int INF = 1e9;
const int mod = 1e9 + 7;
const ll LINF = 1e18;

#define TIMER_START auto start_time = high_resolution_clock::now();
#define TIMER_END auto end_time = high_resolution_clock::now(); \
                  auto duration = duration_cast<milliseconds>(end_time - start_time).count(); \
                  cerr << "\nExecution Time: " << duration << " ms\n";

void fname(const string& task_name) {
    freopen((task_name + ".inp").c_str(), "r", stdin);
    freopen((task_name + ".out").c_str(), "w", stdout);
}
ll power (ll a, ll b) {
    if(b == 0) return 1;
    ll res = power(a, b / 2);
    res = res * res % mod;
    if(b & 1) return res * a % mod;
    return res;
}
int f[505], inv_f[505], sz[1005], sz1[1005];
void add (int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}
ll mul (int x, int y) {
    return (ll)x * y % mod;
}
int dp[2][1005][505], n, a[505], b[505], tot[1005], C[1005][505];
vector<int> comp;
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        comp.eb(a[i]);
        comp.eb(b[i] + 1);
    }
    comp.eb(0);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = comp.size() - 1;
    for (int i = 0; i <= M; i++) {
        if(i < M) {
            sz[i] = min(n, comp[i + 1] - comp[i]);
            sz1[i] = comp[i + 1] - comp[i];
        }
        else {
            sz[i] = sz1[i] = 1;
        }
    }
    for (int i = 0; i <= M; i++) {
        ll tu = 1, mau = 1;
        C[i][0] = 1;
        for (int len = 1; len <= sz[i]; len ++) {
            tu = tu * (sz1[i] - len + 1) % mod;
            mau = mau * len % mod;
            C[i][len] = tu * power(mau, mod - 2) % mod;
        }
    }
    dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        int cur = i & 1, prv = cur ^ 1;
        for (int j = 0; j <= M; ++j) for (int len = 0; len <= sz[j]; ++len) dp[cur][j][len] = 0;
        for (int j = 0; j <= M; j++) {
            for (int len = 0; len <= sz[j]; len ++) {
                add(dp[cur][j][len], dp[prv][j][len]);
            }
        }
        int L = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
        int R = lower_bound(comp.begin(), comp.end(), b[i] + 1) - comp.begin() - 1;
        for (int k = 0; k <= R; k++) {
            if(k > 0) tot[k] = tot[k - 1];
            else tot[k] = 0;
            for (int len = 0; len <= sz[k]; len ++) {
                add(tot[k], mul(dp[prv][k][len], C[k][len]));
            }
        }
        for (int j = L; j <= R; j++) {
//            if(a[i] != b[i] && j == R) continue;
            if(j < R) {
                for (int len = 1; len < sz[j]; len ++) {
                    add(dp[cur][j][len + 1], dp[prv][j][len]);
                }
            }
            add(dp[cur][j][1], tot[j - 1]);
        }
    }
    int ans = 0;
    for (int j = 0; j <= M; j++) {
        for (int len = 0; len <= sz[j]; len ++) {
            add(ans, mul(dp[n & 1][j][len], C[j][len]));
        }
    }
    cout << ans - 1;
}

int32_t main() {
    io;
    // fname("task");
    TIMER_START;
    solve();
    TIMER_END;
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void fname(const std::string&)':
boat.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen((task_name + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen((task_name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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