oj.uz

Submission #501400

# Submission time Handle Problem Language Result Execution time Memory
501400 2022-01-03T05:42:30 Z Abrar_Al_Samit Boat (APIO16_boat) C++17
9 / 100
 2000 ms 40516 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX = 505;
const int uMX = 1e4 + 3;
const int Mod = 1e9 + 7;
int a[MX], b[MX];
int dp[MX][uMX];
int n;
int solve(int i, int prev) {
    if(i>n) return (prev!=0);
    int &ret = dp[i][prev];
    if(ret!=-1) return ret;
    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 ret;
}
void PlayGround() {
    cin >> n;
    vector<tuple<int,int,int>>mapping;
    for(int i=1; i<=n; ++i) {
        cin >> a[i] >> b[i];
        mapping.emplace_back(a[i], b[i], i);
    }
    sort(mapping.begin(), mapping.end());
    int cur(1), sub(0);
    for(int i=0; i<n; ++i) {
        int f, s, id;
        tie(f, s, id) = mapping[i];
        if(f-sub>cur) {
            sub += f-sub-cur;
        }
        cur = max(cur, s-sub+1);
        a[id] = f-sub;
        b[id] = s-sub;
    }
    memset(dp, -1, sizeof dp);
    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 9 ms 20044 KB Output is correct
2 Correct 9 ms 20032 KB Output is correct
3 Correct 9 ms 20044 KB Output is correct
4 Correct 10 ms 20044 KB Output is correct
5 Correct 9 ms 20140 KB Output is correct
6 Correct 9 ms 20016 KB Output is correct
7 Correct 10 ms 20044 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 10 ms 20044 KB Output is correct
10 Correct 10 ms 20044 KB Output is correct
11 Correct 10 ms 20048 KB Output is correct
12 Correct 9 ms 20044 KB Output is correct
13 Correct 10 ms 20036 KB Output is correct
14 Correct 9 ms 20040 KB Output is correct
15 Correct 11 ms 20036 KB Output is correct
16 Correct 9 ms 20052 KB Output is correct
17 Correct 9 ms 20052 KB Output is correct
18 Correct 9 ms 20072 KB Output is correct
19 Correct 9 ms 20044 KB Output is correct
20 Correct 8 ms 20100 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20044 KB Output is correct
2 Correct 9 ms 20032 KB Output is correct
3 Correct 9 ms 20044 KB Output is correct
4 Correct 10 ms 20044 KB Output is correct
5 Correct 9 ms 20140 KB Output is correct
6 Correct 9 ms 20016 KB Output is correct
7 Correct 10 ms 20044 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 10 ms 20044 KB Output is correct
10 Correct 10 ms 20044 KB Output is correct
11 Correct 10 ms 20048 KB Output is correct
12 Correct 9 ms 20044 KB Output is correct
13 Correct 10 ms 20036 KB Output is correct
14 Correct 9 ms 20040 KB Output is correct
15 Correct 11 ms 20036 KB Output is correct
16 Correct 9 ms 20052 KB Output is correct
17 Correct 9 ms 20052 KB Output is correct
18 Correct 9 ms 20072 KB Output is correct
19 Correct 9 ms 20044 KB Output is correct
20 Correct 8 ms 20100 KB Output is correct
21 Execution timed out 2066 ms 20044 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1624 ms 40516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20044 KB Output is correct
2 Correct 9 ms 20032 KB Output is correct
3 Correct 9 ms 20044 KB Output is correct
4 Correct 10 ms 20044 KB Output is correct
5 Correct 9 ms 20140 KB Output is correct
6 Correct 9 ms 20016 KB Output is correct
7 Correct 10 ms 20044 KB Output is correct
8 Correct 9 ms 20044 KB Output is correct
9 Correct 10 ms 20044 KB Output is correct
10 Correct 10 ms 20044 KB Output is correct
11 Correct 10 ms 20048 KB Output is correct
12 Correct 9 ms 20044 KB Output is correct
13 Correct 10 ms 20036 KB Output is correct
14 Correct 9 ms 20040 KB Output is correct
15 Correct 11 ms 20036 KB Output is correct
16 Correct 9 ms 20052 KB Output is correct
17 Correct 9 ms 20052 KB Output is correct
18 Correct 9 ms 20072 KB Output is correct
19 Correct 9 ms 20044 KB Output is correct
20 Correct 8 ms 20100 KB Output is correct
21 Execution timed out 2066 ms 20044 KB Time limit exceeded
22 Halted 0 ms 0 KB -