Submission #1302061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302061		tdkhai	Boat (APIO16_boat)	C++20	100 / 100	435 ms	2440 KiB

boat

/*
        _.-- ,.--.
      .'   .'     /
       @       |'..--------._
     /      \._/              '.
    /  .-.-                     \
   (  /    \                     \
   \\      '.                  | #
    \\       \   -.           /
     :\       |    )._____.'   \
      "       |   /  \  |  \    )
              |   |./'  :__ \.-'
              '--'
*/
#include<bits/stdc++.h>
#define ll long long
#define llll pair<ll,ll>
#define ii pair<int,int>
#define fi first
#define se second
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define ull unsigned long long
#define iii pair<int,ii>
#define iv pair<pii,ii>
#define db double
#define ld long double
#define pb push_back
#define tdk "kfph"


using namespace std;

const int dx[]  = {1, -1, 0, 0};
const int dy[]  = {0, 0, -1, 1};
const int dxx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyy[] = {2, -2, 2, -2, 1, -1, 1, -1};
const ll INF=1e18;
const int mod=1e9+7;
const int N=1e3+5;
int fact[N],inv[N],dp[N][N],a[N],b[N],n,m;
vector<int> val;
int add(int a,int b)
{
    return (a+b)%mod;
}
int mul(int a,int b)
{
    return 1ll*a*b%mod;
}
int sub(int a,int b)
{
    return ((a-b)%mod+mod)%mod;
}
int binpow(int a,int b)
{
    if(b==0) return 1;
    int ans=binpow(a,b/2);
    ans=mul(ans,ans);
    if(b&1) return mul(ans,a);
    return ans;
}
void kfph()
{
    cin >> n;
    fact[0]=1;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i] >> b[i];
        val.pb(a[i]);
        val.pb(b[i]+1);
        fact[i]=mul(fact[i-1],i);
    }
    inv[n]=binpow(fact[n],mod-2);
    for(int i=n-1;i>=0;i--)
    {
        inv[i]=mul(inv[i+1],i+1);
    }
    for(int i=1;i<=n;i++)
    {
        inv[i]=mul(inv[i],fact[i-1]);
    }
    val.pb(0);
    sort(val.begin(),val.end());
    val.erase(unique(val.begin(),val.end()),val.end());
    m=val.size()-1;
    for(int i=0;i<=n;i++)
    {
        dp[i][0]=1;
    }
    for(int j=1;j+1<=m;j++)
    {
        int numrange=val[j+1]-val[j];
        for(int i=0;i<=n;i++)
        {
            dp[i][j]=dp[i][j-1];

            int cnt=0;
            int nck=1;
            for(int k=i;k>=1;k--)
            {
                if(a[k]<=val[j] and val[j+1]<=b[k]+1)
                {
                    cnt++;
                    nck=mul(nck,mul(inv[cnt],numrange+cnt-1));
                    dp[i][j]=add(dp[i][j],mul(dp[k-1][j-1],nck));
                }
            }
        }
    }
    cout << sub(dp[n][m-1],1);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
    //cin >> t;
    while(t--)
    {
        kfph();
    }
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
boat.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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