Submission #1107171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107171		ASN49K	Boat (APIO16_boat)	C++14	100 / 100	1118 ms	4580 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
mt19937 rng(69);
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
int add(int x,int y)
{
    assert(y>=0 && y<mod && x<mod);
    return (x+y)%mod;
}
int pw2(int a,int p)
{
    int rez=1;
    while(p>0)
    {
        if(p&1)
        {
            rez=prod(rez,a);
        }
        p>>=1;
        a=prod(a,a);
    }
    return rez;
}
const int N=500;
int dp[2*N+1][N+1],sum[2*N+1];
int fact[N+1],inv[N+1];
void pre_proc()
{
    fact[0]=1,inv[0]=1;
    for(int i=1;i<=N;i++)
    {
        fact[i]=prod(fact[i-1] , i);
        inv[i]=pw2(fact[i] , mod-2);
    }
}
int comb(int k,int n)
{
    if(k>n)
    {
        return 0;
    }
    int rez=1;
    for(int i=0;i<k;i++)
    {
        rez=prod(rez , n-i);
    }
    return prod(rez,inv[k]);
}
main()
{
    pre_proc();
    int n;
    cin>>n;
    //segmente de forma [x,y)
    vector<pair<int,int>>a(n);

    vector<int>poz(1,0);
    poz.reserve(2*n+1);
    for(auto &c:a)
    {
        cin>>c.first>>c.second;
        c.second++;
        poz.pb(c.first);
        poz.pb(c.second);
    }
    sort(all(poz));
    poz.erase(unique(all(poz)) , poz.end());
    for(int i=0;i<poz.size()-1;i++)
    {
        sum[i]=1;
    }
    dp[0][1]=1;


    vector<vector<int>>combb(poz.size()-1 , vector<int>(n+1));
    for(int i=1;i<poz.size()-1;i++)
    {
        int aux=1;
        for(int j=1;j<=n;j++)
        {
            aux=prod(aux , poz[i+1]-poz[i]-j+1);
            combb[i][j]=prod(aux , inv[j]);
        }
    }
    for(auto &c:a)
    {
        c.first=lower_bound(all(poz) , c.first)-poz.begin();
        c.second=lower_bound(all(poz) , c.second)-poz.begin()-1;
        for(int i=c.first;i<=c.second;i++)
        {
            for(int j=n;j>=2;j--)
            {
                dp[i][j]=add(dp[i][j] , dp[i][j-1]);
            }
            dp[i][1]=add(dp[i][1] , sum[i-1]);
        }
        for(int i=1;i<poz.size()-1;i++)
        {
            sum[i]=sum[i-1];
            for(int j=1;j<=n;j++)
            {
                //if(c.first==2)cout<< prod(dp[i][j] , comb(j,poz[i+1]-poz[i]))<<' ';
                sum[i]=add(sum[i] , prod(dp[i][j] , combb[i][j]));
            }
            //cout<<'\n';
            //cout<<sum[i]<<' ';
        }
        //cout<<'\n';
    }
    cout<<sum[poz.size()-2]-1;
}

Compilation message (stderr)

boat.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | main()
      | ^~~~
boat.cpp: In function 'int main()':
boat.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<poz.size()-1;i++)
      |                 ~^~~~~~~~~~~~~
boat.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=1;i<poz.size()-1;i++)
      |                 ~^~~~~~~~~~~~~
boat.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int i=1;i<poz.size()-1;i++)
      |                     ~^~~~~~~~~~~~~

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