Submission #1247524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247524		horiaboeriu	Boat (APIO16_boat)	C++20	0 / 100	279 ms	10028 KiB

boat

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 500;
const int MOD = 1e9 + 7;
const int INF = 2e9;
int vst[MAXN + 1], vdr[MAXN + 1], nrpos[2 * MAXN + 1][MAXN + 1], combinari[2 * MAXN + 1][MAXN + 1], fact[MAXN + 1], inv[MAXN + 1], dp[MAXN + 1][2 * MAXN + 1], dp2[MAXN + 1][2 * MAXN + 1], sp[MAXN + 1][2 * MAXN + 1];
//nrpos[j][nr] = numarul de moduri sa aleaga nr grupuri barci in intervalul v[j - 1] + 1, v[j] astfel incat sa fie cerscatoare, unii pot sa nu aleaga barci
//pos = v[j] - v[j - 1]
//care este comb(pos, nr) + comb(nr - 1, 1) * comb(pos, nr - 1) + comb(nr - 1, 2) * comb(pos, nr - 2) + ... + comb(nr - 1, nr - 1) * comb(pos, 1) ca pe utlimul o sa il aleg mereu

//combinari[j][nr] = comb(v[j] - v[j - 1], nr) si calculez tot in O(n^2) ca dupa sa le am in O(1) cand calculez nrpos
//dp[i][j] = numarul de moduri sa aduc din primele i grupuri astfel incat grupul i aduce maxim v[j] barci si minim v[j - 1] + 1 barci
//si dp2[i][j] = numarul de moduri sa aduc din primele i grupuri astfel incat grupul i aduce maxim v[j] barci
//dp2 este doar suma pe prefix de la dp
//sp[i][j] = cate grupuri de la 1 la i pot lua j barci
struct nume {
    int val, poz;
} v[2 * MAXN + 1];

char cmp(nume a, nume b) {
    return a.val < b.val;
}
void valPoz(int poz, int val) {
    if (poz % 2 > 0) {
        vst[(poz + 1) / 2] = val;
    } else {
        vdr[poz / 2] = val;
    }
}
int expRapida(int a, int b) {
    int rez;
    rez = 1;
    while (b > 0) {
        if (b % 2 > 0) {
            rez = (long long)rez * a % MOD;
        }
        a = (long long)a * a % MOD;
        b /= 2;
    }
    return rez;
}
int minim(int a, int b) {
    return a < b ? a : b;
}
int comb(int n, int k) {
    return (long long)fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main()
{
    //O(n^3) pentru nrpos si pentru dp
    int n, i, minr, nrv, j, pos, xn, p, nr, sf, rez, k;
    scanf("%d", &n);
    minr = INF;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &v[2 * i].val, &v[2 * i + 1].val);
        v[2 * i].val--;//o sa zic ca trebuie minim vst + 1 si maxim vdr deci il fac exclusiv in stanga ca o sa ma ajute la dp
        v[2 * i].poz = 2 * i + 1;
        v[2 * i + 1].poz = 2 * i + 2;
        minr = minim(minr, minim(v[2 * i].val, v[2 * i + 1].val));
    }
    //normalizare
    v[2 * n].val = minr - 1;//santinela
    sort(v, v + 2 * n + 1, cmp);
    valPoz(v[1].poz, 1);
    xn = 1;
    for (i = 2; i <= 2 * n; i++) {
        if (v[i].val > v[i - 1].val) {
            xn++;
            ///printf("val = %d pozn = %d\n", v[i].val, xn);
        }
        valPoz(v[i].poz, xn);
    }
    //calculez factorialele si inversele modulare pana la n
    fact[0] = inv[0] = 1;
    for (i = 1; i <= n; i++) {
        fact[i] = (long long)fact[i - 1] * i % MOD;
    }
    inv[n] = expRapida(fact[n], MOD - 2);
    for (i = n - 1; i > 0; i--) {
        inv[i] = (long long)inv[i + 1] * (i + 1) % MOD;
    }
    //acum elimin duplicatele din v ca oricum pozitiile nu mai conteaza si valorile normalizate sunt corecte
    nrv = 2;
    for (i = 2; i <= 2 * n; i++) {
        if (v[i].val > v[i - 1].val) {
            v[nrv].val = v[i].val;
            nrv++;
        }
    }
    //construiesc combinari
    for (j = 1; j < nrv; j++) {
        pos = v[j].val - v[j - 1].val;
        combinari[j][0] = 1;
        p = combinari[j][1] = pos;
        minr = minim(pos, n);
        for (nr = 2; nr <= minr; nr++) {
            p = (long long)p * (pos - nr + 1) % MOD;
            combinari[j][nr] = (long long)p * inv[nr] % MOD;
        }
    }
    //contruiesc nrpos
    for (j = 1; j < nrv; j++) {
        ///printf("j = %d v = %d\n", j, v[j].val);
        pos = v[j].val - v[j - 1].val;
        for (nr = 1; nr <= n; nr++) {
            minr = minim(pos, nr - 1);
            for (i = 0; i <= minr; i++) {
                nrpos[j][nr] = (nrpos[j][nr] + (long long)combinari[j][nr - i] * comb(nr - 1, i)) % MOD;
            }
            ///printf("j = %d nr = %d nrpos = %d\n", j, nr, nrpos[j][nr]);
        }
    }
    //constriesc dp
    dp[0][0] = 1;
    for (j = 0; j < nrv; j++) {
        dp2[0][j] = 1;
    }
    rez = 0;
    //in dp am valori la i daca grupul i trimite barci
    for (i = 1; i <= n; i++) {
        //vst si vdr sunt deja cele normalizate
        ///printf("i = %d vst = %d vdr = %d\n", i, vst[i], vdr[i]);
        for (j = 1; j < nrv; j++) {
            sp[i][j] = sp[i - 1][j];
        }
        for (j = vst[i] + 1; j <= vdr[i]; j++) {
            sp[i][j]++;
            for (k = 0; k < i; k++) {
                //acum k este ultimul care alege un numar <= v[j - 1].val
                //si trebuie sa vad cate sunt de la k + 1 la i care pot lua barci din intervalul v[j - 1].val + 1, v[j].val
                //ca restul nu iau barci
                dp[i][j] = (dp[i][j] + (long long)dp2[k][j - 1] * nrpos[j][sp[i][j] - sp[k][j]]) % MOD;
            }
            dp2[i][j] = (dp2[i][j - 1] + dp[i][j]) % MOD;
            ///printf("i = %d j = %d k = %d dp = %d\n", i, j, k, dp[i][j]);
        }
        for (; j < nrv; j++) {
            dp2[i][j] = dp2[i][j - 1];
        }
        rez = (rez + dp2[i][nrv - 1]) % MOD;//in caz ca i este ultimul care aduce barci
    }
    printf("%d\n", rez);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d%d", &v[2 * i].val, &v[2 * i + 1].val);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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