oj.uz

Submission #1107168

# Submission time Handle Problem Language Result Execution time Memory
1107168 2024-10-31T18:15:33 Z ASN49K Boat (APIO16_boat) C++14
27 / 100
 2000 ms 1352 KB 
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define int i64
#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;

    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] , comb(j,poz[i+1]-poz[i])));
            }
            //cout<<'\n';
            //cout<<sum[i]<<' ';
        }
        //cout<<'\n';
    }
    cout<<sum[poz.size()-2]-1;
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 1104 KB Output is correct
2 Correct 437 ms 1128 KB Output is correct
3 Correct 445 ms 1104 KB Output is correct
4 Correct 438 ms 1352 KB Output is correct
5 Correct 436 ms 1236 KB Output is correct
6 Correct 439 ms 1200 KB Output is correct
7 Correct 435 ms 1104 KB Output is correct
8 Correct 438 ms 1212 KB Output is correct
9 Correct 438 ms 1224 KB Output is correct
10 Correct 441 ms 1104 KB Output is correct
11 Correct 439 ms 1104 KB Output is correct
12 Correct 437 ms 1168 KB Output is correct
13 Correct 437 ms 1104 KB Output is correct
14 Correct 437 ms 1104 KB Output is correct
15 Correct 438 ms 1188 KB Output is correct
16 Correct 191 ms 848 KB Output is correct
17 Correct 189 ms 1020 KB Output is correct
18 Correct 189 ms 848 KB Output is correct
19 Correct 189 ms 848 KB Output is correct
20 Correct 197 ms 848 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 516 KB Time limit exceeded
2 Halted 0 ms 0 KB -