oj.uz

Submission #403904

# Submission time Handle Problem Language Result Execution time Memory
403904 2021-05-13T14:53:26 Z sad Boat (APIO16_boat) C++14
9 / 100
 2000 ms 346468 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int dp[502][10009],a[500],b[500];
int n;const int mod=1e9+7;
vector<int>v;
int d(int x,int y)
{
    if(x==n)return 1;
    if(y==v.size())return 1;
    int &u=dp[x][y];
    if(u!=-1)return u;
    u=0;
    u=d(x+1,y);
    if(a[x]<=v[y]&&b[x]>=v[y])
    {
        u+=d(x+1,y+1);u%=mod;
        u+=d(x,y+1);u%=mod;
        u-=d(x+1,y+1);u+=mod;u%=mod;
    }
    else {
        u+=d(x,y+1);u%=mod;u-=d(x+1,y+1);u+=mod;u%=mod;
    }
    return u;
}
set<int>s;
int main()
{
    cin>>n;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        for(int j=a[i];j<=b[i];j++)
        {
            s.insert(j);
        }
    }
    while(s.size()>0)
    {
        v.pb(*s.begin());
        s.erase(s.begin());
    }
    cout<<d(0,0)-1;
}

Compilation message

boat.cpp: In function 'int d(int, int)':
boat.cpp:13:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(y==v.size())return 1;
      |        ~^~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20044 KB Output is correct
2 Correct 16 ms 19956 KB Output is correct
3 Correct 16 ms 20072 KB Output is correct
4 Correct 16 ms 20072 KB Output is correct
5 Correct 18 ms 20020 KB Output is correct
6 Correct 18 ms 19992 KB Output is correct
7 Correct 16 ms 19972 KB Output is correct
8 Correct 16 ms 20044 KB Output is correct
9 Correct 16 ms 20052 KB Output is correct
10 Correct 16 ms 20044 KB Output is correct
11 Correct 16 ms 20044 KB Output is correct
12 Correct 16 ms 20044 KB Output is correct
13 Correct 16 ms 20068 KB Output is correct
14 Correct 16 ms 20072 KB Output is correct
15 Correct 15 ms 20044 KB Output is correct
16 Correct 10 ms 19916 KB Output is correct
17 Correct 11 ms 19908 KB Output is correct
18 Correct 10 ms 19992 KB Output is correct
19 Correct 13 ms 19892 KB Output is correct
20 Correct 11 ms 19916 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20044 KB Output is correct
2 Correct 16 ms 19956 KB Output is correct
3 Correct 16 ms 20072 KB Output is correct
4 Correct 16 ms 20072 KB Output is correct
5 Correct 18 ms 20020 KB Output is correct
6 Correct 18 ms 19992 KB Output is correct
7 Correct 16 ms 19972 KB Output is correct
8 Correct 16 ms 20044 KB Output is correct
9 Correct 16 ms 20052 KB Output is correct
10 Correct 16 ms 20044 KB Output is correct
11 Correct 16 ms 20044 KB Output is correct
12 Correct 16 ms 20044 KB Output is correct
13 Correct 16 ms 20068 KB Output is correct
14 Correct 16 ms 20072 KB Output is correct
15 Correct 15 ms 20044 KB Output is correct
16 Correct 10 ms 19916 KB Output is correct
17 Correct 11 ms 19908 KB Output is correct
18 Correct 10 ms 19992 KB Output is correct
19 Correct 13 ms 19892 KB Output is correct
20 Correct 11 ms 19916 KB Output is correct
21 Correct 110 ms 20632 KB Output is correct
22 Correct 125 ms 20752 KB Output is correct
23 Correct 112 ms 20708 KB Output is correct
24 Correct 113 ms 20584 KB Output is correct
25 Correct 125 ms 20636 KB Output is correct
26 Correct 102 ms 20464 KB Output is correct
27 Correct 101 ms 20352 KB Output is correct
28 Correct 99 ms 20468 KB Output is correct
29 Correct 99 ms 20476 KB Output is correct
30 Incorrect 432 ms 68856 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 20044 KB Output is correct
2 Correct 16 ms 19956 KB Output is correct
3 Correct 16 ms 20072 KB Output is correct
4 Correct 16 ms 20072 KB Output is correct
5 Correct 18 ms 20020 KB Output is correct
6 Correct 18 ms 19992 KB Output is correct
7 Correct 16 ms 19972 KB Output is correct
8 Correct 16 ms 20044 KB Output is correct
9 Correct 16 ms 20052 KB Output is correct
10 Correct 16 ms 20044 KB Output is correct
11 Correct 16 ms 20044 KB Output is correct
12 Correct 16 ms 20044 KB Output is correct
13 Correct 16 ms 20068 KB Output is correct
14 Correct 16 ms 20072 KB Output is correct
15 Correct 15 ms 20044 KB Output is correct
16 Correct 10 ms 19916 KB Output is correct
17 Correct 11 ms 19908 KB Output is correct
18 Correct 10 ms 19992 KB Output is correct
19 Correct 13 ms 19892 KB Output is correct
20 Correct 11 ms 19916 KB Output is correct
21 Correct 110 ms 20632 KB Output is correct
22 Correct 125 ms 20752 KB Output is correct
23 Correct 112 ms 20708 KB Output is correct
24 Correct 113 ms 20584 KB Output is correct
25 Correct 125 ms 20636 KB Output is correct
26 Correct 102 ms 20464 KB Output is correct
27 Correct 101 ms 20352 KB Output is correct
28 Correct 99 ms 20468 KB Output is correct
29 Correct 99 ms 20476 KB Output is correct
30 Incorrect 432 ms 68856 KB Output isn't correct
31 Halted 0 ms 0 KB -