oj.uz

Submission #554077

# Submission time Handle Problem Language Result Execution time Memory
554077 2022-04-27T15:57:48 Z ala2 Boat (APIO16_boat) C++14
9 / 100
 2000 ms 140764 KB 
    #include <bits/stdc++.h>
    //#define int long long
    #define F first
    #define S second
    #define pb push_back
    #define B begin()
    #define E end()

    using namespace std;
    int n;
    int a[1000];
    int b[1000];
    int d[200100];
    map<int,int>m;
    map<pair<int,int>,int>dp;
    const int mod=1e9+7;

    int f(int i,int j)
    {
         if(dp[{i,j}]!=0)
            return dp[{i,j}];

        if(i==n)
            return 1;
        int g=0;
        g+=f(i+1,j);
        if(m[i]!=m[j])
        {
            if(d[i]>d[j])
                g+=f(i+1,i);
            g%=mod;
        }
        return dp[{i,j}]=g%mod;

    }
    signed main()
    {

      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
        //memset(dp,-1,sizeof dp);
        cin>>n;
        int j=1;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            int gg=j;
            for(int k=a[i];k<=b[i];k++)
            {
                m[j]=gg; d[j]=k;
                j++;
            }

        }
        n=j;


        cout<<f(1,0)-1<<endl;



    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8268 KB Output is correct
2 Correct 79 ms 8200 KB Output is correct
3 Correct 89 ms 8236 KB Output is correct
4 Correct 91 ms 8196 KB Output is correct
5 Correct 75 ms 8168 KB Output is correct
6 Correct 87 ms 8184 KB Output is correct
7 Correct 101 ms 8148 KB Output is correct
8 Correct 110 ms 8204 KB Output is correct
9 Correct 87 ms 8260 KB Output is correct
10 Correct 84 ms 8196 KB Output is correct
11 Correct 85 ms 8148 KB Output is correct
12 Correct 93 ms 8248 KB Output is correct
13 Correct 113 ms 8332 KB Output is correct
14 Correct 91 ms 8248 KB Output is correct
15 Correct 85 ms 8256 KB Output is correct
16 Correct 100 ms 8148 KB Output is correct
17 Correct 96 ms 8152 KB Output is correct
18 Correct 82 ms 8180 KB Output is correct
19 Correct 76 ms 8172 KB Output is correct
20 Correct 78 ms 8164 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8268 KB Output is correct
2 Correct 79 ms 8200 KB Output is correct
3 Correct 89 ms 8236 KB Output is correct
4 Correct 91 ms 8196 KB Output is correct
5 Correct 75 ms 8168 KB Output is correct
6 Correct 87 ms 8184 KB Output is correct
7 Correct 101 ms 8148 KB Output is correct
8 Correct 110 ms 8204 KB Output is correct
9 Correct 87 ms 8260 KB Output is correct
10 Correct 84 ms 8196 KB Output is correct
11 Correct 85 ms 8148 KB Output is correct
12 Correct 93 ms 8248 KB Output is correct
13 Correct 113 ms 8332 KB Output is correct
14 Correct 91 ms 8248 KB Output is correct
15 Correct 85 ms 8256 KB Output is correct
16 Correct 100 ms 8148 KB Output is correct
17 Correct 96 ms 8152 KB Output is correct
18 Correct 82 ms 8180 KB Output is correct
19 Correct 76 ms 8172 KB Output is correct
20 Correct 78 ms 8164 KB Output is correct
21 Execution timed out 2099 ms 136140 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8268 KB Output is correct
2 Correct 79 ms 8200 KB Output is correct
3 Correct 89 ms 8236 KB Output is correct
4 Correct 91 ms 8196 KB Output is correct
5 Correct 75 ms 8168 KB Output is correct
6 Correct 87 ms 8184 KB Output is correct
7 Correct 101 ms 8148 KB Output is correct
8 Correct 110 ms 8204 KB Output is correct
9 Correct 87 ms 8260 KB Output is correct
10 Correct 84 ms 8196 KB Output is correct
11 Correct 85 ms 8148 KB Output is correct
12 Correct 93 ms 8248 KB Output is correct
13 Correct 113 ms 8332 KB Output is correct
14 Correct 91 ms 8248 KB Output is correct
15 Correct 85 ms 8256 KB Output is correct
16 Correct 100 ms 8148 KB Output is correct
17 Correct 96 ms 8152 KB Output is correct
18 Correct 82 ms 8180 KB Output is correct
19 Correct 76 ms 8172 KB Output is correct
20 Correct 78 ms 8164 KB Output is correct
21 Execution timed out 2099 ms 136140 KB Time limit exceeded
22 Halted 0 ms 0 KB -