Submission #346704

#	Time	Username	Problem	Language	Result	Execution time	Memory
346704		YJU	Boat (APIO16_boat)	C++14	100 / 100	292 ms	492 KiB

boat

#include <cstdio>
#include <algorithm>
typedef long long ll;
const int MAXN = 500;
const ll MOD = 1000000007LL;
using namespace std;
int top, a[MAXN+1], b[MAXN+1], l[MAXN+1], r[MAXN+1], h[2*MAXN+1], g[MAXN+1];
ll inv[MAXN+1], C[MAXN+1];

int main()
{
    int N;
    scanf("%d", &N);

    inv[1] = 1;
    for (int i = 2; i <= N; ++i)
        inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;

    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &a[i], &b[i]);
        h[2*i-1] = a[i];
        h[2*i] = b[i]+1;
    }
    sort(h+1, h+2*N+1);
    top = unique(h+1, h+2*N+1)-h-1;

    for (int i = 1; i <= N; ++i) { // [l, r)
        l[i] = lower_bound(h+1, h+1+top, a[i])-h;
        r[i] = lower_bound(h+1, h+1+top, b[i]+1)-h;
    }

    g[0] = 1;
    C[0] = 1;
    for (int j = 1; j < top; ++j) {
        int L = h[j+1]-h[j];

        for (int i = 1; i <= N; ++i)
            C[i] = C[i-1]*(L+i-1) %MOD * inv[i] %MOD;

        for (int i = N; i >= 1; --i) {
            if (l[i]<=j && j+1<=r[i]) {
                ll f = 0, m = 1, c = L; // m: p+1~i號學校有多少能選區間j
                for (int p = i-1; p >= 0; --p) {
                    f = (f + c*g[p]) % MOD;
                    if (l[p]<=j && j+1<=r[p])
                        c = C[++m];
                }
                g[i] = (g[i]+f) % MOD;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; ++i)
        ans = (ans+g[i]) % MOD;
    printf("%d", ans);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
boat.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         scanf("%d %d", &a[i], &b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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