Submission #371435

#	Time	Username	Problem	Language	Result	Execution time	Memory
371435		BartolM	Boat (APIO16_boat)	C++17	0 / 100	1818 ms	98588 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];
vector <int> v;
map <int, int> kraj;
int dp[N][2*N][N];
#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) {
    if (kol>siz[gr]) return 0;
    if (gr>=m) return 0;
    if (pos==n) return povrh[gr][kol];

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

    ret=0;
    ret=add(ret, mul(povrh[gr][kol], rek(pos, gr+1, 0))); //nova grupa
    ret=add(ret, rek(pos+1, gr, kol)); //ne stavljam
    if (p[gr].X>=A[pos] && p[gr].Y<=B[pos]) ret=add(ret, rek(pos+1, gr, kol+1));
    #if DEBUG
        printf("pos: %d, gr: %d: kol: %d ===== %d\n", pos, gr, kol, ret);
    #endif //DEBUG
    return ret;
}

void solve() {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m=v.size();

    p[0]=mp(0, v[0]-1);
    for (int i=1; i<m; ++i) p[i]=mp(p[i-1].Y+1, max(v[i]-1+kraj[v[i]], p[i-1].Y+1));
    for (int i=0; i<m; ++i) siz[i]=p[i].Y-p[i].X;

    #if DEBUG
        printf("\n");
        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), MOD-1);
    printf("%d\n", sol);
}

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

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

Compilation message (stderr)

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

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