Submission #315992

#	Time	Username	Problem	Language	Result	Execution time	Memory
315992		phathnv	Boat (APIO16_boat)	C++11	9 / 100	485 ms	6392 KiB

boat

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Boat"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 502;
const int MOD = 1e9 + 7;

int n, a[N], b[N];
int nX, x[2 * N], inv[N], dp[2][N * 2][N], sumDp[N * 2][N];

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
}

void compress(){
    for(int i = 1; i <= n; i++){
        x[++nX] = a[i];
        x[++nX] = ++b[i];
    }
    sort(x + 1, x + 1 + nX);
    nX = unique(x + 1, x + 1 + nX) - (x + 1);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(x + 1, x + 1 + nX, a[i]) - x;
        b[i] = lower_bound(x + 1, x + 1 + nX, b[i]) - x;
    }
}

int powMod(int x, int k){
    if (k == 0)
        return 1;
    int res = powMod(x, k >> 1);
    res = (ll) res * res % MOD;
    if (k & 1)
        res = (ll) res * x % MOD;
    return res;
}

void prepare(){
    for(int i = 1; i <= n; i++)
        b[i]--;
    inv[0] = 1;
    for(int i = 1; i <= n; i++)
        inv[i] = powMod(i, MOD - 2);
}

void add(int &x, int y){
    x += y;
    x -= (x >= MOD) * MOD;
}

void solve(){
    for(int i = 0; i < n; i++){
        int id = i & 1;
        for(int j = 1; j < nX; j++){
            int len = min(n, x[j + 1] - x[j]);
            for(int k = 1; k <= len; k++)
                dp[id ^ 1][j][k] = 0;
        }

        int sum = 1;
        for(int j = 1; j < nX; j++){
            int len = min(n, x[j + 1] - x[j]);
            if (a[i + 1] <= j && j <= b[i + 1])
                add(dp[id ^ 1][j][1], (ll) sum * len % MOD);
            for(int k = 1; k <= len; k++){
                add(sum, sumDp[j][k]);
                if (a[i + 1] <= j && j <= b[i + 1] && k < len)
                    add(dp[id ^ 1][j][k + 1], (ll) sumDp[j][k] * (len - k) % MOD * inv[k + 1] % MOD);
            }
        }
        for(int j = 1; j < nX; j++){
            int len = min(n, x[j + 1] - x[j]);
            for(int k = 1; k <= len; k++)
                add(sumDp[j][k], dp[id ^ 1][j][k]);
        }
    }

    int res = 0;
    for(int j = 1; j < nX; j++){
        int len = min(n, x[j + 1] - x[j]);
        for(int k = 1; k <= len; k++)
            add(res, sumDp[j][k]);
    }
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    compress();
    prepare();
    solve();
    return 0;
}

Compilation message (stderr)

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

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