Submission #102785

#	Time	Username	Problem	Language	Result	Execution time	Memory
102785		alexpetrescu	Boat (APIO16_boat)	C++14	100 / 100	605 ms	1532 KiB

boat

#include <cstdio>
#include <algorithm>
#include <vector>

//FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w");
#define fin stdin
#define fout stdout

#define MOD 1000000007

inline void precalcCombinari(std::vector < std::vector < int > > &comb) {
    for (int i = 0; i < (int)comb.size(); i++) {
        comb[i][0] = 1;
        for (int j = 1; j <= i; j++)
            comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
    }
}

inline bool getValues(int n, int a, int b, std::vector < int > &A, std::vector < int > &B, std::vector < bool > &avem) {
    bool ans = 0;
    for (int i = 1; i <= n; i++) {
        avem[i] = A[i] <= a && B[i] >= b - 1;
        ans |= avem[i];
    }
    return ans;
}

inline int lgput(int a, int n) {
    int r = 1;
    while (n) {
        if (n % 2)
            r = 1LL * r * a % MOD;
        a = 1LL * a * a % MOD;
        n /= 2;
    }
    return r;
}

inline void calcCombinari(std::vector < int > &comb, int n) {
    comb[0] = 1;
    for (int i = 1; i < (int)comb.size(); i++)
        comb[i] = 1LL * comb[i - 1] * (n - i + 1) % MOD * lgput(i, MOD - 2) % MOD;
}

inline void precalc(std::vector < int > &r, int tmax, int l, std::vector < std::vector < int > > &comb) {
    std::vector < int > combL(std::min(tmax + 1, l + 1));
    calcCombinari(combL, l);

    for (int i = 0; i <= tmax; i++) {
        r[i] = 0;
        for (int j = 1; j <= i && j <= l; j++)
            r[i] = (r[i] + 1LL * comb[i - 1][j - 1] * combL[j]) % MOD;
    }
}

inline void solve(std::vector < std::vector < int > > &dp, int n, int l, int &w, int &q, std::vector < bool > &avem, std::vector < std::vector < int > > &comb) {
    w = 1 - w;
    q = 1 - q;

    int tmax = 0;
    for (int i = 1; i <= n; i++)
        tmax += avem[i];

    std::vector < int > r(tmax + 1);
    precalc(r, tmax, l, comb);

    for (int i = 0; i <= n; i++)
        dp[w][i] = 0;

    for (int i = 0; i <= n; i++) {
        dp[w][i] = (dp[w][i] + dp[q][i]) % MOD;
        int t = 0;
        for (int j = i + 1; j <= n; j++) {
            if (avem[j]) {
                t++;
                dp[w][j] = (dp[w][j] + 1LL * dp[q][i] * r[t]) % MOD;
            }
        }
    }
}

int main() {
    int n;
    fscanf(fin, "%d", &n);

    std::vector < std::vector < int > > comb(n, std::vector < int > (n, 0));
    precalcCombinari(comb);

    std::vector < int > poz, A(n + 1), B(n + 1);
    for (int i = 1; i <= n; i++) {
        fscanf(fin, "%d%d", &A[i], &B[i]);
        poz.push_back(A[i]);
        poz.push_back(B[i] + 1);
    }

    std::sort(poz.begin(), poz.end());
    poz.resize(std::distance(poz.begin(), std::unique(poz.begin(), poz.end())));

    int w = 0, q = 1;
    std::vector < std::vector < int > > dp(2, std::vector < int > (n + 1, 0));
    dp[0][0] = 1;
    std::vector < bool > avem(n + 1);
    for (int i = 0; i < (int)poz.size() - 1; i++)
        if (getValues(n, poz[i], poz[i + 1], A, B, avem))
            solve(dp, n, poz[i + 1] - poz[i], w, q, avem, comb);

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + dp[w][i]) % MOD;

    fprintf(fout, "%d\n", ans);

    fclose(fin);
    fclose(fout);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:84:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fin, "%d", &n);
     ~~~~~~^~~~~~~~~~~~~~~
boat.cpp:91:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fin, "%d%d", &A[i], &B[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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