oj.uz

Submission #501356

# Submission time Handle Problem Language Result Execution time Memory
501356 2022-01-02T21:22:53 Z Abrar_Al_Samit Boat (APIO16_boat) C++17
9 / 100
 2000 ms 8240 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX = 505;
const int Mod = 1e9 + 7;
int a[MX], b[MX];
map<pair<int,int>,int>dp;
int n;
int solve(int i, int prev) {
    if(i>n) return (prev!=0);
    if(dp.count(make_pair(i, prev))) return dp[make_pair(i, prev)]; 
    int ret = 0;
    ret = solve(i+1, prev);
    for(int cur=max(a[i], prev+1); cur<=b[i]; ++cur) {
        ret += solve(i+1, cur);
        if(ret>=Mod) ret -= Mod;
    }
    return dp[make_pair(i, prev)] = ret;
}
void PlayGround() {
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> a[i] >> b[i];
    }   
    cout << solve(1, 0) << endl;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    PlayGround();
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8180 KB Output is correct
2 Correct 49 ms 8096 KB Output is correct
3 Correct 49 ms 8124 KB Output is correct
4 Correct 49 ms 8132 KB Output is correct
5 Correct 53 ms 8080 KB Output is correct
6 Correct 65 ms 8064 KB Output is correct
7 Correct 62 ms 8180 KB Output is correct
8 Correct 68 ms 8104 KB Output is correct
9 Correct 74 ms 8240 KB Output is correct
10 Correct 67 ms 8152 KB Output is correct
11 Correct 63 ms 8064 KB Output is correct
12 Correct 66 ms 8112 KB Output is correct
13 Correct 65 ms 8132 KB Output is correct
14 Correct 63 ms 8168 KB Output is correct
15 Correct 69 ms 8160 KB Output is correct
16 Correct 11 ms 2508 KB Output is correct
17 Correct 12 ms 2768 KB Output is correct
18 Correct 12 ms 2636 KB Output is correct
19 Correct 12 ms 2728 KB Output is correct
20 Correct 12 ms 2488 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8180 KB Output is correct
2 Correct 49 ms 8096 KB Output is correct
3 Correct 49 ms 8124 KB Output is correct
4 Correct 49 ms 8132 KB Output is correct
5 Correct 53 ms 8080 KB Output is correct
6 Correct 65 ms 8064 KB Output is correct
7 Correct 62 ms 8180 KB Output is correct
8 Correct 68 ms 8104 KB Output is correct
9 Correct 74 ms 8240 KB Output is correct
10 Correct 67 ms 8152 KB Output is correct
11 Correct 63 ms 8064 KB Output is correct
12 Correct 66 ms 8112 KB Output is correct
13 Correct 65 ms 8132 KB Output is correct
14 Correct 63 ms 8168 KB Output is correct
15 Correct 69 ms 8160 KB Output is correct
16 Correct 11 ms 2508 KB Output is correct
17 Correct 12 ms 2768 KB Output is correct
18 Correct 12 ms 2636 KB Output is correct
19 Correct 12 ms 2728 KB Output is correct
20 Correct 12 ms 2488 KB Output is correct
21 Execution timed out 2076 ms 2588 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 2077 ms 204 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8180 KB Output is correct
2 Correct 49 ms 8096 KB Output is correct
3 Correct 49 ms 8124 KB Output is correct
4 Correct 49 ms 8132 KB Output is correct
5 Correct 53 ms 8080 KB Output is correct
6 Correct 65 ms 8064 KB Output is correct
7 Correct 62 ms 8180 KB Output is correct
8 Correct 68 ms 8104 KB Output is correct
9 Correct 74 ms 8240 KB Output is correct
10 Correct 67 ms 8152 KB Output is correct
11 Correct 63 ms 8064 KB Output is correct
12 Correct 66 ms 8112 KB Output is correct
13 Correct 65 ms 8132 KB Output is correct
14 Correct 63 ms 8168 KB Output is correct
15 Correct 69 ms 8160 KB Output is correct
16 Correct 11 ms 2508 KB Output is correct
17 Correct 12 ms 2768 KB Output is correct
18 Correct 12 ms 2636 KB Output is correct
19 Correct 12 ms 2728 KB Output is correct
20 Correct 12 ms 2488 KB Output is correct
21 Execution timed out 2076 ms 2588 KB Time limit exceeded
22 Halted 0 ms 0 KB -