Submission #203708

#	Time	Username	Problem	Language	Result	Execution time	Memory
203708		dsabolic	Boat (APIO16_boat)	C++17	100 / 100	558 ms	4856 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
#define per(i, n, a) for(int (i) = (n) - 1; (i) >= (a); --(i))
#define trav(i, x) for(auto& (i) : (x))
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
mt19937 mrand(random_device{}());

const int INF = 0x3f3f3f3f;
const int OFF = 1 << 20;
const int MOD = (int)1e9 + 7;
const int N = 550;

int n;
pii q[N];
vector<int> comp;
ll dist[2 * N];
ll dp[N][2 * N];
ll inv [N];

ll add(ll a, ll b) {
    return (a + b) % MOD;
}

ll binpow(ll base, int exp) {
        ll ret = 1;
        while(exp) {
                if(exp & 1) {
                        ret = (ret * base) % MOD;
                        if(!ret) return ret;
                }

                exp >>= 1;
                base = (base * base) % MOD;
        }

        return ret;
}
int main() {
    scanf("%d", &n);
    rep(i, 1, n + 1) {
        scanf("%d%d", &q[i].X, &q[i].Y);
        comp.pb(q[i].X); comp.pb(q[i].Y + 1);
    }
    sort(all(comp));

    comp.erase(unique(all(comp)), comp.end());

        rep(i, 2, n + 1) inv[i] = binpow(i, MOD - 2);
    rep(i, 1, n + 1) {
        q[i].X = lower_bound(all(comp), q[i].X) - comp.begin() + 1;
        q[i].Y = lower_bound(all(comp), q[i].Y + 1) - comp.begin();
    }

    dist[0] = comp[0];
    rep(i, 1, SZ(comp)) dist[i] = comp[i] - comp[i - 1];

    //printf("compsz %d\n", SZ(comp));
    rep(j, 0, SZ(comp)) dp[0][j] = 1;
    rep(i, 1, n + 1) { // fiksiramo prefix
        dp[i][0] = 1;
        //printf("for %d is [%d,%d]\n", i, q[i].X, q[i].Y);
        rep(j, q[i].X, q[i].Y + 1) { // fiksiramo kraj
            dp[i][j] = add(dp[i][j], (dp[i - 1][j - 1] * dist[j]) % MOD); // ako samo sebe uzimamo
            //printf("dp[%d][%d] -> %lld\n", i, j, dp[i][j]);

            ll binom = dist[j] - 1; int cnt = 1;
            per(k, i, 1) {
                if(j >= q[k].X && j <= q[k].Y) {
                                        binom = (binom * (dist[j] - 1 + cnt)) % MOD;
                                        if(!binom) break;
                                        binom = (binom * inv[++cnt]) % MOD;

                    dp[i][j] = add(dp[i][j], (dp[k - 1][j - 1] * binom) % MOD);
                }
            }
        }

        rep(j, 1, SZ(comp))
            dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
    }

    printf("%lld\n", ((ll)dp[n][SZ(comp) - 1] - 1 + MOD) % MOD);

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &q[i].X, &q[i].Y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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