Submission #203418

#	Time	Username	Problem	Language	Result	Execution time	Memory
203418		dsabolic	Boat (APIO16_boat)	C++17	9 / 100	131 ms	8952 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 binom[2 * N][N];

ll add(ll a, ll b) {
    if(a + b >= MOD) return a + b - MOD;
    return a + b;
}

void gen_pascal() {
    binom[0][0] = 1;
    rep(i, 1, SZ(comp)) {
        binom[i][0] = 1;

        rep(j, 1, i + 1)
            binom[i][j] = add(binom[i - 1][j], binom[i - 1][j - 1]);
    }
}
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));
    gen_pascal();

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

    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();
    }
    rep(i, 1, SZ(comp)) dist[i] = comp[i] - comp[i - 1];

    rep(j, 0, SZ(comp)) dp[0][j] = 1;
    rep(i, 1, n + 1) { // fiksiramo prefix
        dp[i][0] = 1;
        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] -> %d\n", i, j, dp[i][j]);

            int cnt = 1;
            per(k, i, 1) {
                if(j >= q[k].X && j <= q[k].Y) {
                    dp[i][j] = add(dp[i][j], (dp[k - 1][j - 1] * binom[dist[j]][++cnt]) % 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;
    }

    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:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:50: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: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42