oj.uz

Submission #403931

# Submission time Handle Problem Language Result Execution time Memory
403931 2021-05-13T15:17:40 Z sad Boat (APIO16_boat) C++14
9 / 100
 2000 ms 301932 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;v.pb(0);
    for(int i=1; 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());
    }
    for(int i=0;i<v.size();i++)dp[0][i]=1;
    for(int i=0;i<n+1;i++)dp[i][0]=1;
    for(int i=1; i<n+1; i++)
    {
        for(int j=1; j<v.size(); j++)
        {int u=0;
            u+=dp[i-1][j];
            u%=mod;int x=i,y=j;
            if(a[i]<=v[j]&&b[i]>=v[j])
            {
                u+=dp[x-1][y-1];//cout<<u<<endl;
                u%=mod;
                u+=dp[x][y-1];//cout<<dp[x][y-1]<<endl;
                u%=mod;
                u-=dp[x-1][y-1];
                u+=mod;
                u%=mod;
            }
            else
            {
                u+=dp[x][y-1];
                u%=mod;
                u-=dp[x-1][y-1];
                u+=mod;
                u%=mod;
            }
        dp[i][j]=u;u=0;
        }
    }
    cout<<dp[n][v.size()-1]-1;
}

Compilation message

boat.cpp: In function 'int d(int, int)':
boat.cpp:15:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if(y==v.size())
      |        ~^~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<v.size();i++)dp[0][i]=1;
      |                 ~^~~~~~~~~
boat.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j=1; j<v.size(); j++)
      |                      ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3276 KB Output is correct
2 Correct 6 ms 3276 KB Output is correct
3 Correct 6 ms 3276 KB Output is correct
4 Correct 6 ms 3276 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 5 ms 3276 KB Output is correct
7 Correct 6 ms 3304 KB Output is correct
8 Correct 5 ms 3276 KB Output is correct
9 Correct 6 ms 3276 KB Output is correct
10 Correct 5 ms 3276 KB Output is correct
11 Correct 6 ms 3276 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 7 ms 3276 KB Output is correct
14 Correct 6 ms 3336 KB Output is correct
15 Correct 7 ms 3276 KB Output is correct
16 Correct 3 ms 2508 KB Output is correct
17 Correct 3 ms 2508 KB Output is correct
18 Correct 3 ms 2508 KB Output is correct
19 Correct 3 ms 2508 KB Output is correct
20 Correct 3 ms 2508 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3276 KB Output is correct
2 Correct 6 ms 3276 KB Output is correct
3 Correct 6 ms 3276 KB Output is correct
4 Correct 6 ms 3276 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 5 ms 3276 KB Output is correct
7 Correct 6 ms 3304 KB Output is correct
8 Correct 5 ms 3276 KB Output is correct
9 Correct 6 ms 3276 KB Output is correct
10 Correct 5 ms 3276 KB Output is correct
11 Correct 6 ms 3276 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 7 ms 3276 KB Output is correct
14 Correct 6 ms 3336 KB Output is correct
15 Correct 7 ms 3276 KB Output is correct
16 Correct 3 ms 2508 KB Output is correct
17 Correct 3 ms 2508 KB Output is correct
18 Correct 3 ms 2508 KB Output is correct
19 Correct 3 ms 2508 KB Output is correct
20 Correct 3 ms 2508 KB Output is correct
21 Correct 78 ms 12728 KB Output is correct
22 Correct 67 ms 12684 KB Output is correct
23 Correct 65 ms 12692 KB Output is correct
24 Correct 67 ms 12696 KB Output is correct
25 Correct 67 ms 12692 KB Output is correct
26 Correct 57 ms 10060 KB Output is correct
27 Correct 57 ms 10076 KB Output is correct
28 Correct 68 ms 10064 KB Output is correct
29 Correct 61 ms 10060 KB Output is correct
30 Execution timed out 2093 ms 57912 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3276 KB Output is correct
2 Correct 6 ms 3276 KB Output is correct
3 Correct 6 ms 3276 KB Output is correct
4 Correct 6 ms 3276 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 5 ms 3276 KB Output is correct
7 Correct 6 ms 3304 KB Output is correct
8 Correct 5 ms 3276 KB Output is correct
9 Correct 6 ms 3276 KB Output is correct
10 Correct 5 ms 3276 KB Output is correct
11 Correct 6 ms 3276 KB Output is correct
12 Correct 6 ms 3276 KB Output is correct
13 Correct 7 ms 3276 KB Output is correct
14 Correct 6 ms 3336 KB Output is correct
15 Correct 7 ms 3276 KB Output is correct
16 Correct 3 ms 2508 KB Output is correct
17 Correct 3 ms 2508 KB Output is correct
18 Correct 3 ms 2508 KB Output is correct
19 Correct 3 ms 2508 KB Output is correct
20 Correct 3 ms 2508 KB Output is correct
21 Correct 78 ms 12728 KB Output is correct
22 Correct 67 ms 12684 KB Output is correct
23 Correct 65 ms 12692 KB Output is correct
24 Correct 67 ms 12696 KB Output is correct
25 Correct 67 ms 12692 KB Output is correct
26 Correct 57 ms 10060 KB Output is correct
27 Correct 57 ms 10076 KB Output is correct
28 Correct 68 ms 10064 KB Output is correct
29 Correct 61 ms 10060 KB Output is correct
30 Execution timed out 2093 ms 57912 KB Time limit exceeded
31 Halted 0 ms 0 KB -