Submission #1301453

#TimeUsernameProblemLanguageResultExecution timeMemory
1301453daveleBoat (APIO16_boat)C++20
100 / 100
485 ms16044 KiB
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;

const int mod = 1e9+7;
void add (int &a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a = 1ll*a*b%mod;
}

template<class X, class Y>
    bool minimize(X &x, const Y&y){
        if (x<=y) return false;
        else{
            x = y;
            return true;
        }
    }
template<class X, class Y>
    bool maximize (X &x, const Y&y){
        if (x>=y) return false;
        else{
            x = y;
            return true;
        }
    }

/////////////////////////////////////////////////////////////////////////////////

//// dang nhap ham
//#ifndef davele
//
//#endif // davele
//
//// chay thu ham main:
//
//#ifdef davele
//
//#endif // davele

////////////////////////////////////////////////////////////////////////////
//const int lim = , limit = , inf = ;
const string name = "boat";
const int lim = 1050, limit = lim+5;

int powe (int coso, int somu){
    int ret = 1;
    while (somu>0){
        if (somu&1) mul (ret, coso);
        mul (coso, coso);
        somu>>=1;
    }
    return ret;
}

vector <int> ds;
int L[limit], R[limit], numrange;
int sum[limit][limit];
vector <int> inside[limit];
int dp[limit][limit];
int sumdp[limit][limit];
int prep[limit][limit];
int n;
int inv[limit];
int C[limit][limit];


void compress(){
    ds.pb(-1);
    for (int i=1; i<=n; i++){
        ds.pb(L[i]);
        ds.pb(R[i]+1);
    }
    sort (ds.begin(), ds.end());
    ds.erase (unique(ds.begin(), ds.end()), ds.end());
    ds.pb(ds.back()+1);
    // range[i] = [ds[i]; ds[i+1]-1]
    //
    numrange = ds.size()-2;
//    for (int i=1; i<=numrange; i++) cerr<<ds[i]<<" "<<ds[i+1]<<"\n";
}

void process(){
    compress();
    //
    for (int i=1; i<=n; i++){
        for (int j=1; j<=numrange; j++){
            sum[i][j] = sum[i-1][j];
//            cerr<<L[i]<<" "<<R[i]<<" "<<" "<<j<<"\n";
            if (L[i]<=ds[j] && ds[j+1]-1<=R[i]){
                inside[i].pb(j);
//                cerr<<i<<" "<<j<<"\n";
                sum[i][j]++;
            }
        }
    }
    // sum[i][j] : xet den nguoi thu i, co bao nhieu team co the nam trong range j
    // C[k][n]
    for (int i=0; i<=lim; i++) C[0][i] = 1;
    for (int i=1; i<=lim; i++) for (int j=1; j<=i; j++){
        C[j][i] = (C[j-1][i-1] + C[j][i-1])%mod;
    }
    for (int i=1; i<=lim; i++) inv[i] = powe (i, mod-2);
    // prep[kind][cnt] : so cach chon phu hop sao cho voi cnt team thi team cuoi cung chac chan
    // duoc chon
    // prep[kind][cnt] = sum (C(k-1, cnt-1)*C(k, lenrange)) voi k chay tu 1 den min(cnt, lenrange)
    for (int kind = 1; kind<=numrange; kind++){
        int lenrange = ds[kind+1]-ds[kind];
        for (int cnt = 1; cnt<=sum[n][kind]; cnt++){
            int mx = min(cnt, lenrange);
            int tu = 1, mau = 1;
            for (int chose = 1; chose<=mx; chose++){
                mul (tu, lenrange-chose+1);
                mul (mau, inv[chose]);
                add (prep[kind][cnt], 1ll*C[chose-1][cnt-1]*tu%mod*mau%mod);
            }
//            cerr<<kind<<" "<<cnt<<" "<<prep[kind][cnt]<<"\n";
        }
    }

    // dp[i][j] : den vi tri i, so cach chon sao cho o group i co chon nguoi o range j
    int ret = 0;
    dp[0][0] = 1;
    for (int i=0; i<=lim; i++) sumdp[0][i] = 1;
    for (int i=1; i<=n; i++){
        for (int x:inside[i]){
            for (int j=0; j<i; j++){
                add (dp[i][x], 1ll*sumdp[j][x-1]*prep[x][sum[i][x]-sum[j][x]]%mod);
            }
            add (ret, dp[i][x]);
        }
        for (int j=1; j<=numrange; j++) sumdp[i][j] = (sumdp[i][j-1]+dp[i][j])%mod;
    }
    cout<<ret;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //
    if (fopen((name+".inp").c_str(), "r")){
        freopen ((name+".inp").c_str(), "r", stdin);
        freopen ((name+".out").c_str(), "w", stdout);
    }
    //
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>L[i]>>R[i];
    }
    process();
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:169:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen ((name+".inp").c_str(), "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:170:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen ((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...