Submission #52966

#	Time	Username	Problem	Language	Result	Execution time	Memory
52966		chpipis	Boat (APIO16_boat)	C++11	100 / 100	1915 ms	11452 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 505;
const int MOD = 1e9 + 7;

inline int mul_mod(int a, int b) {
    return a * 1LL * b % MOD;
}

inline void add_mod(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

int mpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = mul_mod(res, a);
        a = mul_mod(a, a);
        b >>= 1;
    }
    return res;
}

int a[MAXN], b[MAXN];
int s[2 * MAXN];
int nCr[2 * MAXN][MAXN];
int dp[2][2 * MAXN][MAXN][2];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int n;
    scanf("%d", &n);
    vi pts = {0};
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i], &b[i]);
        pts.pb(a[i]);
        pts.pb(b[i]);
    }
    sort(all(pts));
    pts.resize(unique(all(pts)) - pts.begin());
    int m = (int)pts.size() - 1;
    for (int j = 1; j <= m; j++)
        s[j] = pts[j] - pts[j - 1] - 1;
    for (int j = 0; j <= m; j++) {
        nCr[j][0] = 1;
        for (int k = 1; k <= n; k++) {
            if (k > s[j]) {
                nCr[j][k] = 0;
            } else {
                nCr[j][k] = mul_mod(
                    mul_mod(s[j] - k + 1, mpow(k, MOD - 2)),
                    nCr[j][k - 1]);
            }
        }
    }
    for (int j = 0; j <= m; j++)
        dp[0 & 1][j][0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i & 1][0][0][0] = 1;
        for (int j = 1; j <= m + (i == n); j++) {
            dp[i & 1][j][0][0] = 0;
            for (int z = 0; z <= i; z++) {
                add_mod(dp[i & 1][j][0][0], mul_mod(dp[i & 1][j - 1][z][0], nCr[j - 1][z]));
                if (z > 0)
                    add_mod(dp[i & 1][j][0][0], mul_mod(dp[i & 1][j - 1][z][1], nCr[j - 1][z - 1]));
            }
            if (j == m + 1) continue;
            for (int k = 1; k <= i; k++) {
                for (int f = 0; f <= 1; f++) {
                    dp[i & 1][j][k][f] = 0;
                    add_mod(dp[i & 1][j][k][f], dp[(i - 1) & 1][j][k][f]);
                    if (f == 1 && a[i] <= pts[j] && b[i] >= pts[j])
                        add_mod(dp[i & 1][j][k][f], dp[(i - 1) & 1][j][k - 1][0]);
                    else if (f == 0 && a[i] < pts[j] && b[i] >= pts[j])
                        add_mod(dp[i & 1][j][k][f], dp[(i - 1) & 1][j][k - 1][f]);
                }
            }
        }
    }
    printf("%d\n", (dp[n & 1][m + 1][0][0] + MOD - 1) % MOD);
    return 0;
}

Compilation message (stderr)

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

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