oj.uz

Submission #252017

# Submission time Handle Problem Language Result Execution time Memory
252017 2020-07-23T17:03:42 Z DS007 Boat (APIO16_boat) C++14
9 / 100
 980 ms 20180 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 500, mod = 1e9 + 7;
int a[N], b[N];
int dp[2][N * N * 3];
int n;

int solveTestCase() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];

    vector<int> v = {0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++)
            v.push_back(a[i] + j), v.push_back(a[i] - j), v.push_back(b[i] + j), v.push_back(b[i] - j);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
        b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
    }

    for (int i = a[0]; i <= b[0]; i++)
        dp[0][i] = 1;

    for (int i = 1; i < n; i++) {
        int sum = 1;
        for (int j = 0; j < a[i]; j++)
            dp[i%2][j] = dp[(i - 1)%2][j], sum += dp[(i - 1)%2][j], sum %= mod;
        for (int j = b[i] + 1; j < N * N * 3; j++)
            dp[i%2][j] = dp[(i - 1)%2][j];

        for (int j = a[i]; j <= b[i]; j++)
            sum +=  dp[(i - 1)%2][j], sum %= mod, dp[i%2][j] = sum;
    }

    int ans = 0;
    for (int i = 1; i < N * N * 3; i++)
        ans += dp[(n - 1)%2][i], ans %= mod;

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

boat.cpp: In function 'long long int solveTestCase()':
boat.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 20052 KB Output is correct
2 Correct 941 ms 20056 KB Output is correct
3 Correct 907 ms 20052 KB Output is correct
4 Correct 922 ms 20052 KB Output is correct
5 Correct 928 ms 20052 KB Output is correct
6 Correct 933 ms 20052 KB Output is correct
7 Correct 980 ms 20048 KB Output is correct
8 Correct 915 ms 20056 KB Output is correct
9 Correct 966 ms 20048 KB Output is correct
10 Correct 951 ms 20052 KB Output is correct
11 Correct 938 ms 20052 KB Output is correct
12 Correct 922 ms 20052 KB Output is correct
13 Correct 933 ms 20052 KB Output is correct
14 Correct 907 ms 20052 KB Output is correct
15 Correct 906 ms 20052 KB Output is correct
16 Correct 541 ms 20052 KB Output is correct
17 Correct 622 ms 20052 KB Output is correct
18 Correct 578 ms 20056 KB Output is correct
19 Correct 595 ms 20052 KB Output is correct
20 Correct 555 ms 20052 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 20052 KB Output is correct
2 Correct 941 ms 20056 KB Output is correct
3 Correct 907 ms 20052 KB Output is correct
4 Correct 922 ms 20052 KB Output is correct
5 Correct 928 ms 20052 KB Output is correct
6 Correct 933 ms 20052 KB Output is correct
7 Correct 980 ms 20048 KB Output is correct
8 Correct 915 ms 20056 KB Output is correct
9 Correct 966 ms 20048 KB Output is correct
10 Correct 951 ms 20052 KB Output is correct
11 Correct 938 ms 20052 KB Output is correct
12 Correct 922 ms 20052 KB Output is correct
13 Correct 933 ms 20052 KB Output is correct
14 Correct 907 ms 20052 KB Output is correct
15 Correct 906 ms 20052 KB Output is correct
16 Correct 541 ms 20052 KB Output is correct
17 Correct 622 ms 20052 KB Output is correct
18 Correct 578 ms 20056 KB Output is correct
19 Correct 595 ms 20052 KB Output is correct
20 Correct 555 ms 20052 KB Output is correct
21 Correct 500 ms 20052 KB Output is correct
22 Correct 504 ms 20052 KB Output is correct
23 Correct 502 ms 20052 KB Output is correct
24 Correct 552 ms 20052 KB Output is correct
25 Correct 547 ms 20180 KB Output is correct
26 Correct 539 ms 20116 KB Output is correct
27 Correct 589 ms 20180 KB Output is correct
28 Correct 490 ms 20052 KB Output is correct
29 Correct 505 ms 20056 KB Output is correct
30 Incorrect 882 ms 20052 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 12540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 906 ms 20052 KB Output is correct
2 Correct 941 ms 20056 KB Output is correct
3 Correct 907 ms 20052 KB Output is correct
4 Correct 922 ms 20052 KB Output is correct
5 Correct 928 ms 20052 KB Output is correct
6 Correct 933 ms 20052 KB Output is correct
7 Correct 980 ms 20048 KB Output is correct
8 Correct 915 ms 20056 KB Output is correct
9 Correct 966 ms 20048 KB Output is correct
10 Correct 951 ms 20052 KB Output is correct
11 Correct 938 ms 20052 KB Output is correct
12 Correct 922 ms 20052 KB Output is correct
13 Correct 933 ms 20052 KB Output is correct
14 Correct 907 ms 20052 KB Output is correct
15 Correct 906 ms 20052 KB Output is correct
16 Correct 541 ms 20052 KB Output is correct
17 Correct 622 ms 20052 KB Output is correct
18 Correct 578 ms 20056 KB Output is correct
19 Correct 595 ms 20052 KB Output is correct
20 Correct 555 ms 20052 KB Output is correct
21 Correct 500 ms 20052 KB Output is correct
22 Correct 504 ms 20052 KB Output is correct
23 Correct 502 ms 20052 KB Output is correct
24 Correct 552 ms 20052 KB Output is correct
25 Correct 547 ms 20180 KB Output is correct
26 Correct 539 ms 20116 KB Output is correct
27 Correct 589 ms 20180 KB Output is correct
28 Correct 490 ms 20052 KB Output is correct
29 Correct 505 ms 20056 KB Output is correct
30 Incorrect 882 ms 20052 KB Output isn't correct
31 Halted 0 ms 0 KB -