Submission #371466

#	Time	Username	Problem	Language	Result	Execution time	Memory
371466		BartolM	Boat (APIO16_boat)	C++17	0 / 100	60 ms	13292 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=505;
const int MOD=1e9+7;

int n, m;
int A[N], B[N], povrh[2*N][N], siz[2*N];
pii p[2*N];
set <pii> S;
int dp[2][2*N][N][2];
#define DEBUG 0

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

int mul(int a, int b) {
    return (ll)a*b%MOD;
}

int pot(int baza, int ex) {
    int ret=1;
    while (ex) {
        if (ex%2) ret=mul(ret, baza);
        baza=mul(baza, baza);
        ex/=2;
    }
    return ret;
}

int divv(int a, int b) {
    return mul(a, pot(b, MOD-2));
}

void prec() {
    for (int i=0; i<m; ++i) {
        povrh[i][0]=1;
        for (int j=1; j<=min(n, siz[i]); ++j) povrh[i][j]=divv(mul(povrh[i][j-1], siz[i]-j+1), j);
    }
}

void solve() {
//    p[0]=mp(0, S.begin()->X-1);
    m=0;
    for (auto it=S.begin(); it!=S.end(); ++it) {
        if (it==S.begin()) continue;
        auto pr=it; pr--;
        p[m++]=mp(pr->X+pr->Y, it->X-!(it->Y));
    }
    for (int i=0; i<m; ++i) siz[i]=p[i].Y-p[i].X+1;

    #if DEBUG
        printf("m == %d\n", m);
        for (int i=0; i<m; ++i) printf("[%d, %d]\n", p[i].X, p[i].Y);
    #endif // DEBUG

    prec();

    int b=0;
    for (int gr=0; gr<m; ++gr) {
        for (int kol=1; kol<=siz[gr]; ++kol) {
            for (int fl=0; fl<=1; ++fl) dp[b][gr][kol][fl]=povrh[gr][kol];
        }
    }
    b^=1;
    for (int i=n-1; i>=0; --i) {
        memset(dp[b], 0, sizeof dp[b]);
        for (int gr=m-1; gr>=0; --gr) {
            for (int kol=0; kol<=min(siz[gr], i+1); ++kol) {
                for (int fl=0; fl<=1; ++fl) {
                    int &ret=dp[b][gr][kol][fl];
                    ret=0;
                    ret=add(ret, mul(povrh[gr][kol], dp[b][gr+1][0][0]));
                    if (fl) ret=add(ret, dp[!b][gr][kol][1]);
                    if (p[gr].X>=A[i] && p[gr].Y<=B[i])
                        ret=add(ret, dp[!b][gr][kol+1][1]);
                }
            }
        }
        b^=1;
    }

//    int sol=add(rek(0, 0, 0, 1), MOD-1);
    printf("%d\n", dp[!b][0][0][1]);
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i) {
        scanf("%d %d", &A[i], &B[i]);
        S.insert(mp(A[i], 0));
        S.insert(mp(B[i], 1));
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void load()':
boat.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         scanf("%d %d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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