oj.uz

Submission #1073922

# Submission time Handle Problem Language Result Execution time Memory
1073922 2024-08-25T03:29:13 Z RiverFlow Boat (APIO16_boat) C++14
31 / 100
 360 ms 4268 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)500 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int n, a[N], b[N];

namespace SUB1 {
int dp[N][N];
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
void sol() {
    dp[0][0] = 1;
    a[0] = b[0] = 0;
    FOR(i, 0, n - 1) FOR(j, 0, i) if (dp[i][j]) {
        add(dp[i + 1][j], dp[i][j]);
        if (b[i + 1] > b[j])
            add(dp[i + 1][i + 1], dp[i][j]);
    }
    int res = 0;
    FOR(i, 1, n) add(res, dp[n][i]);
    cout << res;
}
};

namespace SUB2 {
int S[N];
vector<int> dp[N];
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}

void sol() {
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        int os = 1;
        int L = b[i] - a[i] + 1;
        S[i] = L;
        dp[i].resize(L);
        for(int j = 1; j < i; ++j) {
            if (a[i] > b[j]) {
                add(os, dp[j][S[j] - 1]);
            } else if (max(a[i], a[j]) <= min(b[i], b[j])) {
                if (a[i] >= a[j]) {
                    for(int x = 0; x < L; ++x) {
                        if (x + a[i] - a[j] - 1 >= 0)
                            add(dp[i][x], dp[j][min(x + a[i] - a[j] - 1, S[j] - 1)]);
                    }
                } else {
                    for(int x = a[j] + 1; x <= b[i]; ++x) {
                        add(dp[i][x - a[i]], dp[j][min(x - a[j] - 1, S[j] - 1)]);
                    }
                }
            }
        }
        for(int x = 0; x < L; ++x) {
            add(dp[i][x], os);
            if (x > 0) add(dp[i][x], dp[i][x - 1]);
        }
        add(res, dp[i][L - 1]);
    }
    cout << res;
}
};
void main_code() {
    cin >> n;
    long long sum = 0;
    for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i], sum += b[i] - a[i] + 1;
    if (n <= 500 and sum == n) {
        return SUB1::sol(), void();
    }
    if (n <= 500 and sum <= (int)1e6 + 7) {
        return SUB2::sol(), void();
    }
}


/*     Let the river flows naturally     */

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1368 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1256 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1368 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1256 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 213 ms 3864 KB Output is correct
22 Correct 205 ms 3692 KB Output is correct
23 Correct 193 ms 3492 KB Output is correct
24 Correct 213 ms 3920 KB Output is correct
25 Correct 214 ms 3920 KB Output is correct
26 Correct 328 ms 4016 KB Output is correct
27 Correct 340 ms 4180 KB Output is correct
28 Correct 328 ms 4216 KB Output is correct
29 Correct 360 ms 4220 KB Output is correct
30 Correct 6 ms 4188 KB Output is correct
31 Correct 6 ms 4068 KB Output is correct
32 Correct 7 ms 4208 KB Output is correct
33 Correct 7 ms 4188 KB Output is correct
34 Correct 8 ms 4268 KB Output is correct
35 Correct 5 ms 3932 KB Output is correct
36 Correct 6 ms 4256 KB Output is correct
37 Correct 6 ms 4188 KB Output is correct
38 Correct 6 ms 3932 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1368 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 1372 KB Output is correct
10 Correct 1 ms 1372 KB Output is correct
11 Correct 1 ms 1256 KB Output is correct
12 Correct 1 ms 1372 KB Output is correct
13 Correct 1 ms 1372 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1372 KB Output is correct
16 Correct 1 ms 1372 KB Output is correct
17 Correct 1 ms 1372 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 1 ms 1372 KB Output is correct
21 Correct 213 ms 3864 KB Output is correct
22 Correct 205 ms 3692 KB Output is correct
23 Correct 193 ms 3492 KB Output is correct
24 Correct 213 ms 3920 KB Output is correct
25 Correct 214 ms 3920 KB Output is correct
26 Correct 328 ms 4016 KB Output is correct
27 Correct 340 ms 4180 KB Output is correct
28 Correct 328 ms 4216 KB Output is correct
29 Correct 360 ms 4220 KB Output is correct
30 Correct 6 ms 4188 KB Output is correct
31 Correct 6 ms 4068 KB Output is correct
32 Correct 7 ms 4208 KB Output is correct
33 Correct 7 ms 4188 KB Output is correct
34 Correct 8 ms 4268 KB Output is correct
35 Correct 5 ms 3932 KB Output is correct
36 Correct 6 ms 4256 KB Output is correct
37 Correct 6 ms 4188 KB Output is correct
38 Correct 6 ms 3932 KB Output is correct
39 Incorrect 0 ms 348 KB Output isn't correct
40 Halted 0 ms 0 KB -