Submission #371462

#	Time	Username	Problem	Language	Result	Execution time	Memory
371462		BartolM	Boat (APIO16_boat)	C++17	27 / 100	2075 ms	28448 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=105;
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[N][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);
    }
}

int rek(int pos, int gr, int kol, int fl) {
    if (kol>siz[gr]) return 0;
    if (gr>=m) return 0;
    if (pos==n) return (!!kol)*povrh[gr][kol];

    int &ret=dp[pos][gr][kol][fl];
    if (ret!=-1) return ret;

    ret=0;
    ret=add(ret, mul(povrh[gr][kol], rek(pos, gr+1, 0, 0))); //nova grupa
    if (fl) ret=add(ret, rek(pos+1, gr, kol, 1)); //ne stavljam
    if (p[gr].X>=A[pos] && p[gr].Y<=B[pos]) ret=add(ret, rek(pos+1, gr, kol+1, 1));

    #if DEBUG
        printf("pos: %d, gr: %d, kol: %d, fl: %d ===== %d\n", pos, gr, kol, fl, ret);
    #endif //DEBUG

    return ret;
}

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();

    memset(dp, -1, sizeof dp);
//    int sol=add(rek(0, 0, 0, 1), MOD-1);
    printf("%d\n", rek(0, 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:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |         scanf("%d %d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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