Submission #487453

#	Time	Username	Problem	Language	Result	Execution time	Memory
487453		leaked	Boat (APIO16_boat)	C++14	100 / 100	1427 ms	7364 KiB

boat

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
const int M=1e9+7;
const int N=5e2+10;
const int Mx=200+1;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
int inv[N];
int gi(int x){
    if(!inv[x]) inv[x]=binpow(x,M-2);
    return inv[x];
}
int C(int k,int n){
    if(k>n) return 0;
    int ans=1;
    for(int i=n-k+1;i<=n;i++) ans=mult(ans,i);
    for(int i=1;i<=k;i++) ans=mult(ans,gi(i));
    return ans;
}
signed main(){
    fast_iati;
    int tests=1;
    while(tests--){
        int n=200;
        cin>>n;
        vec<int>a(n),b(n);
        vec<int> kek;
        for(int i=0;i<n;i++) {
            cin>>a[i]>>b[i];
//            a[i]=rand()%Mx+1,b[i]=rand()%Mx+1;
//            if(a[i]>b[i]) swap(a[i],b[i]);
            kek.pb(a[i]-1),kek.pb(b[i]);
        }
        vec<int>l,r;l=a;r=b;
        auto solve=[&](){
            kek.pb(0);sort(all(kek));kek.erase(unique(all(kek)),kek.end());
            vec<vec<int>>dp(n+1,vec<int>(sz(kek)+1,0));
            vec<vec<int>>pref(n+1,vec<int>(sz(kek)+1,0));
            vec<int>ways(sz(kek));
            vec<vec<int>>col(sz(kek),vec<int>(n+1,0));
            vec<vec<int>>cnk(n+1,vec<int>(n+1,0));
            cnk[0][0]=1;
            for(int i=1;i<=n;i++){
                for(int j=0;j<=i;j++){
                    cnk[i][j]=cnk[i-1][j];
                    if(j)
                        add(cnk[i][j],cnk[i-1][j-1]);
                }
            }
            for(int i=1;i<sz(kek);i++){
                ways[i]=kek[i]-kek[i-1];
                vec<int> ct(n+1,0);
                ct[0]=1;
                for(int j=1;j<=n;j++){
                    if(j>ways[i]) ct[j]=0;
                    else{
                        ct[j]=mult(ct[j-1],ways[i]-j+1);
                        ct[j]=mult(ct[j],gi(j));
                    }
//                    cout<<"DEBUGFGEEGEGE"<<"C "<<j<<' '<<ways[i]<<' '<<ct[j]<<' '<<endl;
                }
                /// so
                col[i][2]=ct[2];
//                cout<<ct[2]<<endl;
//                cout<<endl;
//                cout<<"YEA "<<ways[]
                for(int j=3;j<=n;j++){
//                    col[i][j]=col[i][j-1];
//                    col[i][j]=mult(col[i][j],j-2);
//                    add(col[i][j],ct[j]);
                    int fuck=0;
                    for(int t=2;t<=j;t++){
                        add(col[i][j],mult(ct[t],cnk[j-2][t-2]));
//                        cout<<"SHE "<<mult(C(t,ways[i]),C(t-2,j-2))<<endl;
                    }

//                    cout<<"DEBIL "<<ways[i]<<' '<<j<<' '<<col[i][j]<<' '<<fuck<<endl;
                }
//                cout<<endl;
            }
            for(int j=0;j<sz(kek);j++) pref[0][j]=1;
            for(int i=0;i<n;i++){
                a[i]=lower_bound(all(kek),a[i]-1)-kek.begin()+1;
                b[i]=lower_bound(all(kek),b[i])-kek.begin();
            }
            for(int i=0;i<n;i++){
                for(int j=a[i];j<=b[i];j++){
                    /// I start with me
                    /// then it's pref[i][j-1]
                    add(dp[i+1][j],mult(ways[j],pref[i][j-1]));
//                    if(i==1)cout<<"ALO "<<pref[i][j-1]<<endl;
                    if(ways[j]>=2){
                        int cnt=1;
                        for(int k=i-1;k>=0;k--){
                            if(a[k]>j || b[k]<j) continue;
                            cnt++;
//                            cout<<"CHECK "<<i<<' '<<k<<' '<<j<<' '<<' '<<col[j][cnt]<<' '<<pref[k][j-1]<<endl;
                            add(dp[i+1][j],mult(col[j][cnt],pref[k][j-1]));
                        }
                    }
                }
//                 for(int j=0;j<sz(kek);j++){
//                    cout<<"DEBUG "<<(j?kek[j-1]+1:0)<<' '<<kek[j]<<' '<<dp[i+1][j]<<endl;
//                }
//                cout<<endl;
                for(int j=0;j<sz(kek);j++){
                    pref[i+1][j]=dp[i+1][j];
                    if(j)add(pref[i+1][j],pref[i+1][j-1]);
                }
                for(int j=0;j<sz(kek);j++){
                    add(pref[i+1][j],pref[i][j]);
                }
            }
            return pref[n][sz(kek)-1];
        };
        auto stupid=[&](){
            vec<vec<int>>dp1(n+1,vec<int>(Mx+1,0));
            for(int j=0;j<=Mx;j++) dp1[0][j]=1;
            for(int i=0;i<n;i++){
//                cout<<"AUE "<<l[i]<<' '<<r[i]<<endl;
                for(int x=l[i];x<=r[i];x++){
                    add(dp1[i+1][x],dp1[i][x-1]);
                }
                for(int j=1;j<=Mx;j++)add(dp1[i+1][j],dp1[i+1][j-1]);
//                cout<<endl;
                for(int j=0;j<=Mx;j++){
                    add(dp1[i+1][j],dp1[i][j]);
                }
            }
            return dp1[n][Mx];
        };
        int rans=solve();
        add(rans,-1);
        cout<<rans;
//        cout<<"SOL "<<stupid()<<' '<<solve()<<endl;
//        int x=solve(),y=stupid();
//        if(x!=y){
//            cout<<y<<' '<<x<<endl;
//            cout<<n<<endl;
//            for(int i=0;i<n;i++) cout<<l[i]<<' '<<r[i]<<endl;
//            return 0;
//        }
    }
    return 0;
}

Compilation message (stderr)

boat.cpp: In lambda function:
boat.cpp:102:25: warning: unused variable 'fuck' [-Wunused-variable]
  102 |                     int fuck=0;
      |                         ^~~~
boat.cpp: In function 'int main()':
boat.cpp:147:14: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  147 |         auto stupid=[&](){
      |              ^~~~~~

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