oj.uz

Submission #1107170

# Submission time Handle Problem Language Result Execution time Memory
1107170 2024-10-31T18:22:32 Z ASN49K Boat (APIO16_boat) C++14
100 / 100
 1195 ms 8360 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;


    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

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:86: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]
   86 |     for(int i=1;i<poz.size()-1;i++)
      |                 ~^~~~~~~~~~~~~
boat.cpp:107: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]
  107 |         for(int i=1;i<poz.size()-1;i++)
      |                     ~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 8264 KB Output is correct
2 Correct 999 ms 8168 KB Output is correct
3 Correct 998 ms 8140 KB Output is correct
4 Correct 999 ms 8268 KB Output is correct
5 Correct 991 ms 8240 KB Output is correct
6 Correct 986 ms 8256 KB Output is correct
7 Correct 988 ms 8264 KB Output is correct
8 Correct 986 ms 8264 KB Output is correct
9 Correct 988 ms 8316 KB Output is correct
10 Correct 996 ms 8264 KB Output is correct
11 Correct 994 ms 8264 KB Output is correct
12 Correct 992 ms 8252 KB Output is correct
13 Correct 999 ms 8344 KB Output is correct
14 Correct 1004 ms 8224 KB Output is correct
15 Correct 992 ms 8224 KB Output is correct
16 Correct 176 ms 1864 KB Output is correct
17 Correct 188 ms 1864 KB Output is correct
18 Correct 182 ms 1824 KB Output is correct
19 Correct 188 ms 1956 KB Output is correct
20 Correct 183 ms 1864 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 8264 KB Output is correct
2 Correct 999 ms 8168 KB Output is correct
3 Correct 998 ms 8140 KB Output is correct
4 Correct 999 ms 8268 KB Output is correct
5 Correct 991 ms 8240 KB Output is correct
6 Correct 986 ms 8256 KB Output is correct
7 Correct 988 ms 8264 KB Output is correct
8 Correct 986 ms 8264 KB Output is correct
9 Correct 988 ms 8316 KB Output is correct
10 Correct 996 ms 8264 KB Output is correct
11 Correct 994 ms 8264 KB Output is correct
12 Correct 992 ms 8252 KB Output is correct
13 Correct 999 ms 8344 KB Output is correct
14 Correct 1004 ms 8224 KB Output is correct
15 Correct 992 ms 8224 KB Output is correct
16 Correct 176 ms 1864 KB Output is correct
17 Correct 188 ms 1864 KB Output is correct
18 Correct 182 ms 1824 KB Output is correct
19 Correct 188 ms 1956 KB Output is correct
20 Correct 183 ms 1864 KB Output is correct
21 Correct 1016 ms 7456 KB Output is correct
22 Correct 1022 ms 7724 KB Output is correct
23 Correct 1008 ms 7844 KB Output is correct
24 Correct 997 ms 7560 KB Output is correct
25 Correct 1016 ms 7596 KB Output is correct
26 Correct 1050 ms 7240 KB Output is correct
27 Correct 1062 ms 7512 KB Output is correct
28 Correct 1044 ms 7164 KB Output is correct
29 Correct 1049 ms 7240 KB Output is correct
30 Correct 1004 ms 8264 KB Output is correct
31 Correct 1000 ms 8280 KB Output is correct
32 Correct 986 ms 8092 KB Output is correct
33 Correct 992 ms 8288 KB Output is correct
34 Correct 987 ms 8116 KB Output is correct
35 Correct 993 ms 8128 KB Output is correct
36 Correct 1006 ms 8196 KB Output is correct
37 Correct 996 ms 8324 KB Output is correct
38 Correct 991 ms 8276 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1360 KB Output is correct
2 Correct 10 ms 1404 KB Output is correct
3 Correct 11 ms 1376 KB Output is correct
4 Correct 11 ms 1360 KB Output is correct
5 Correct 10 ms 1412 KB Output is correct
6 Correct 11 ms 1360 KB Output is correct
7 Correct 11 ms 1360 KB Output is correct
8 Correct 11 ms 1360 KB Output is correct
9 Correct 11 ms 1360 KB Output is correct
10 Correct 11 ms 1392 KB Output is correct
11 Correct 11 ms 1416 KB Output is correct
12 Correct 10 ms 1360 KB Output is correct
13 Correct 10 ms 1360 KB Output is correct
14 Correct 10 ms 1360 KB Output is correct
15 Correct 12 ms 1412 KB Output is correct
16 Correct 7 ms 848 KB Output is correct
17 Correct 6 ms 848 KB Output is correct
18 Correct 6 ms 1020 KB Output is correct
19 Correct 7 ms 848 KB Output is correct
20 Correct 6 ms 848 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 997 ms 8264 KB Output is correct
2 Correct 999 ms 8168 KB Output is correct
3 Correct 998 ms 8140 KB Output is correct
4 Correct 999 ms 8268 KB Output is correct
5 Correct 991 ms 8240 KB Output is correct
6 Correct 986 ms 8256 KB Output is correct
7 Correct 988 ms 8264 KB Output is correct
8 Correct 986 ms 8264 KB Output is correct
9 Correct 988 ms 8316 KB Output is correct
10 Correct 996 ms 8264 KB Output is correct
11 Correct 994 ms 8264 KB Output is correct
12 Correct 992 ms 8252 KB Output is correct
13 Correct 999 ms 8344 KB Output is correct
14 Correct 1004 ms 8224 KB Output is correct
15 Correct 992 ms 8224 KB Output is correct
16 Correct 176 ms 1864 KB Output is correct
17 Correct 188 ms 1864 KB Output is correct
18 Correct 182 ms 1824 KB Output is correct
19 Correct 188 ms 1956 KB Output is correct
20 Correct 183 ms 1864 KB Output is correct
21 Correct 1016 ms 7456 KB Output is correct
22 Correct 1022 ms 7724 KB Output is correct
23 Correct 1008 ms 7844 KB Output is correct
24 Correct 997 ms 7560 KB Output is correct
25 Correct 1016 ms 7596 KB Output is correct
26 Correct 1050 ms 7240 KB Output is correct
27 Correct 1062 ms 7512 KB Output is correct
28 Correct 1044 ms 7164 KB Output is correct
29 Correct 1049 ms 7240 KB Output is correct
30 Correct 1004 ms 8264 KB Output is correct
31 Correct 1000 ms 8280 KB Output is correct
32 Correct 986 ms 8092 KB Output is correct
33 Correct 992 ms 8288 KB Output is correct
34 Correct 987 ms 8116 KB Output is correct
35 Correct 993 ms 8128 KB Output is correct
36 Correct 1006 ms 8196 KB Output is correct
37 Correct 996 ms 8324 KB Output is correct
38 Correct 991 ms 8276 KB Output is correct
39 Correct 10 ms 1360 KB Output is correct
40 Correct 10 ms 1404 KB Output is correct
41 Correct 11 ms 1376 KB Output is correct
42 Correct 11 ms 1360 KB Output is correct
43 Correct 10 ms 1412 KB Output is correct
44 Correct 11 ms 1360 KB Output is correct
45 Correct 11 ms 1360 KB Output is correct
46 Correct 11 ms 1360 KB Output is correct
47 Correct 11 ms 1360 KB Output is correct
48 Correct 11 ms 1392 KB Output is correct
49 Correct 11 ms 1416 KB Output is correct
50 Correct 10 ms 1360 KB Output is correct
51 Correct 10 ms 1360 KB Output is correct
52 Correct 10 ms 1360 KB Output is correct
53 Correct 12 ms 1412 KB Output is correct
54 Correct 7 ms 848 KB Output is correct
55 Correct 6 ms 848 KB Output is correct
56 Correct 6 ms 1020 KB Output is correct
57 Correct 7 ms 848 KB Output is correct
58 Correct 6 ms 848 KB Output is correct
59 Correct 1136 ms 8268 KB Output is correct
60 Correct 1115 ms 8264 KB Output is correct
61 Correct 1112 ms 8352 KB Output is correct
62 Correct 1108 ms 8216 KB Output is correct
63 Correct 1108 ms 8292 KB Output is correct
64 Correct 1168 ms 8284 KB Output is correct
65 Correct 1181 ms 8252 KB Output is correct
66 Correct 1171 ms 8360 KB Output is correct
67 Correct 1173 ms 8264 KB Output is correct
68 Correct 1195 ms 8280 KB Output is correct
69 Correct 1107 ms 8336 KB Output is correct
70 Correct 1099 ms 8188 KB Output is correct
71 Correct 1098 ms 8344 KB Output is correct
72 Correct 1113 ms 8348 KB Output is correct
73 Correct 1120 ms 8348 KB Output is correct
74 Correct 206 ms 1872 KB Output is correct
75 Correct 205 ms 1872 KB Output is correct
76 Correct 208 ms 1872 KB Output is correct
77 Correct 205 ms 1872 KB Output is correct
78 Correct 201 ms 1900 KB Output is correct