oj.uz

Submission #554025

# Submission time Handle Problem Language Result Execution time Memory
554025 2022-04-27T14:56:18 Z ala2 Boat (APIO16_boat) C++14
9 / 100
 2000 ms 363256 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];
    map<pair<pair<int,int>,int>,int>dp;
    //map<pair<pair<int,int>,int>,int>go;
    const int mod=1e9+7;
    //dp[ { {i,last},pl } ]
    int T;
    long long  f(int i,int last,int pl)
    {


        if(dp[ { {i,last},pl } ]!=0)
            return dp[ { {i,last},pl } ]%mod;

        T++;

        if(i==n+1)
            return 1;
        long long g=f(i+1,last,pl);
        for(int j=a[i];j<=b[i];j++)
        if(j>a[last]+pl)
            g+=f(i+1,i,j-a[i]);
        //cout<<"        "<<i<<"   "<<last<<"   "<<pl<<endl;
        //go[ { {i,last},pl } ]=1;
        return dp[ { {i,last},pl } ]=g%mod;
    }
    signed main()
    {
        T=0;
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
        //memset(dp,-1,sizeof dp);
        cin>>n;
        for(int i=1;i<=n;i++){
            //a[i]=n-i;
            cin>>a[i]>>b[i];
        }
            cout<<f(1,0,0)-1<<endl;
        // cout<<T<<endl;
    }

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8148 KB Output is correct
2 Correct 70 ms 8136 KB Output is correct
3 Correct 71 ms 8180 KB Output is correct
4 Correct 75 ms 8172 KB Output is correct
5 Correct 68 ms 8212 KB Output is correct
6 Correct 80 ms 8228 KB Output is correct
7 Correct 79 ms 8148 KB Output is correct
8 Correct 82 ms 8224 KB Output is correct
9 Correct 78 ms 8232 KB Output is correct
10 Correct 77 ms 8244 KB Output is correct
11 Correct 82 ms 8228 KB Output is correct
12 Correct 78 ms 8192 KB Output is correct
13 Correct 76 ms 8184 KB Output is correct
14 Correct 78 ms 8192 KB Output is correct
15 Correct 79 ms 8232 KB Output is correct
16 Correct 72 ms 8224 KB Output is correct
17 Correct 71 ms 8240 KB Output is correct
18 Correct 71 ms 8196 KB Output is correct
19 Correct 71 ms 8196 KB Output is correct
20 Correct 78 ms 8204 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8148 KB Output is correct
2 Correct 70 ms 8136 KB Output is correct
3 Correct 71 ms 8180 KB Output is correct
4 Correct 75 ms 8172 KB Output is correct
5 Correct 68 ms 8212 KB Output is correct
6 Correct 80 ms 8228 KB Output is correct
7 Correct 79 ms 8148 KB Output is correct
8 Correct 82 ms 8224 KB Output is correct
9 Correct 78 ms 8232 KB Output is correct
10 Correct 77 ms 8244 KB Output is correct
11 Correct 82 ms 8228 KB Output is correct
12 Correct 78 ms 8192 KB Output is correct
13 Correct 76 ms 8184 KB Output is correct
14 Correct 78 ms 8192 KB Output is correct
15 Correct 79 ms 8232 KB Output is correct
16 Correct 72 ms 8224 KB Output is correct
17 Correct 71 ms 8240 KB Output is correct
18 Correct 71 ms 8196 KB Output is correct
19 Correct 71 ms 8196 KB Output is correct
20 Correct 78 ms 8204 KB Output is correct
21 Execution timed out 2070 ms 2612 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 2080 ms 363256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8148 KB Output is correct
2 Correct 70 ms 8136 KB Output is correct
3 Correct 71 ms 8180 KB Output is correct
4 Correct 75 ms 8172 KB Output is correct
5 Correct 68 ms 8212 KB Output is correct
6 Correct 80 ms 8228 KB Output is correct
7 Correct 79 ms 8148 KB Output is correct
8 Correct 82 ms 8224 KB Output is correct
9 Correct 78 ms 8232 KB Output is correct
10 Correct 77 ms 8244 KB Output is correct
11 Correct 82 ms 8228 KB Output is correct
12 Correct 78 ms 8192 KB Output is correct
13 Correct 76 ms 8184 KB Output is correct
14 Correct 78 ms 8192 KB Output is correct
15 Correct 79 ms 8232 KB Output is correct
16 Correct 72 ms 8224 KB Output is correct
17 Correct 71 ms 8240 KB Output is correct
18 Correct 71 ms 8196 KB Output is correct
19 Correct 71 ms 8196 KB Output is correct
20 Correct 78 ms 8204 KB Output is correct
21 Execution timed out 2070 ms 2612 KB Time limit exceeded
22 Halted 0 ms 0 KB -