oj.uz

Submission #315985

# Submission time Handle Problem Language Result Execution time Memory
315985 2020-10-24T16:52:32 Z phathnv Boat (APIO16_boat) C++11
9 / 100
 341 ms 4352 KB 
#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second
#define taskname "Boat"

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 502;
const int MOD = 1e9 + 7;

int n, a[N], b[N];
int nX, x[2 * N], inv[N], dp[2][N * 2][N];

void readInput(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
}

void compress(){
    for(int i = 1; i <= n; i++){
        x[++nX] = a[i];
        x[++nX] = ++b[i];
    }
    sort(x + 1, x + 1 + nX);
    nX = unique(x + 1, x + 1 + nX) - (x + 1);
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(x + 1, x + 1 + nX, a[i]) - x;
        b[i] = lower_bound(x + 1, x + 1 + nX, b[i]) - x;
    }
}

int powMod(int x, int k){
    if (k == 0)
        return 1;
    int res = powMod(x, k >> 1);
    res = (ll) res * res % MOD;
    if (k & 1)
        res = (ll) res * x % MOD;
    return res;
}

void prepare(){
    for(int i = 1; i <= n; i++)
        b[i]--;
    inv[0] = 1;
    for(int i = 1; i <= n; i++)
        inv[i] = powMod(i, MOD - 2);
}

void add(int &x, int y){
    x += y;
    x -= (x >= MOD) * MOD;
}

void solve(){
    for(int i = 0; i < n; i++){
        int id = i & 1;
        for(int j = 1; j < nX; j++){
            int len = min(n, x[j + 1] - x[j]);
            for(int k = 1; k <= len; k++)
                dp[id ^ 1][j][k] = 0;
        }

        int sum = 1;
        for(int j = 1; j < nX; j++){
            int len = min(n, x[j + 1] - x[j]);
            if (a[i + 1] <= j && j <= b[i + 1])
                add(dp[id ^ 1][j][1], (ll) sum * len % MOD);
            for(int k = 1; k <= len; k++){
                add(sum, dp[id][j][k]);
                add(dp[id ^ 1][j][k], dp[id][j][k]);
                if (a[i + 1] <= j && j <= b[i + 1] && k < len)
                    add(dp[id ^ 1][j][k + 1], (ll) dp[id][j][k] * (len - k) % MOD * inv[k + 1] % MOD);
            }
        }
    }

    int res = 0;
    for(int j = 1; j < nX; j++){
        int len = min(n, x[j + 1] - x[j]);
        for(int k = 1; k <= len; k++)
            add(res, dp[n & 1][j][k]);
    }
    cout << res;
}

int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    readInput();
    compress();
    prepare();
    solve();
    return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4292 KB Output is correct
2 Correct 335 ms 4344 KB Output is correct
3 Correct 331 ms 4344 KB Output is correct
4 Correct 336 ms 4344 KB Output is correct
5 Correct 333 ms 4344 KB Output is correct
6 Correct 333 ms 4304 KB Output is correct
7 Correct 324 ms 4224 KB Output is correct
8 Correct 333 ms 4344 KB Output is correct
9 Correct 327 ms 4352 KB Output is correct
10 Correct 330 ms 4344 KB Output is correct
11 Correct 341 ms 4224 KB Output is correct
12 Correct 333 ms 4344 KB Output is correct
13 Correct 327 ms 4344 KB Output is correct
14 Correct 334 ms 4224 KB Output is correct
15 Correct 327 ms 4224 KB Output is correct
16 Correct 58 ms 1024 KB Output is correct
17 Correct 62 ms 1152 KB Output is correct
18 Correct 60 ms 1024 KB Output is correct
19 Correct 62 ms 1144 KB Output is correct
20 Correct 60 ms 1024 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4292 KB Output is correct
2 Correct 335 ms 4344 KB Output is correct
3 Correct 331 ms 4344 KB Output is correct
4 Correct 336 ms 4344 KB Output is correct
5 Correct 333 ms 4344 KB Output is correct
6 Correct 333 ms 4304 KB Output is correct
7 Correct 324 ms 4224 KB Output is correct
8 Correct 333 ms 4344 KB Output is correct
9 Correct 327 ms 4352 KB Output is correct
10 Correct 330 ms 4344 KB Output is correct
11 Correct 341 ms 4224 KB Output is correct
12 Correct 333 ms 4344 KB Output is correct
13 Correct 327 ms 4344 KB Output is correct
14 Correct 334 ms 4224 KB Output is correct
15 Correct 327 ms 4224 KB Output is correct
16 Correct 58 ms 1024 KB Output is correct
17 Correct 62 ms 1152 KB Output is correct
18 Correct 60 ms 1024 KB Output is correct
19 Correct 62 ms 1144 KB Output is correct
20 Correct 60 ms 1024 KB Output is correct
21 Correct 26 ms 3960 KB Output is correct
22 Correct 26 ms 3968 KB Output is correct
23 Correct 26 ms 3840 KB Output is correct
24 Correct 28 ms 3840 KB Output is correct
25 Correct 27 ms 3840 KB Output is correct
26 Correct 23 ms 3840 KB Output is correct
27 Correct 23 ms 3840 KB Output is correct
28 Correct 23 ms 3712 KB Output is correct
29 Correct 26 ms 3968 KB Output is correct
30 Incorrect 314 ms 4304 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4292 KB Output is correct
2 Correct 335 ms 4344 KB Output is correct
3 Correct 331 ms 4344 KB Output is correct
4 Correct 336 ms 4344 KB Output is correct
5 Correct 333 ms 4344 KB Output is correct
6 Correct 333 ms 4304 KB Output is correct
7 Correct 324 ms 4224 KB Output is correct
8 Correct 333 ms 4344 KB Output is correct
9 Correct 327 ms 4352 KB Output is correct
10 Correct 330 ms 4344 KB Output is correct
11 Correct 341 ms 4224 KB Output is correct
12 Correct 333 ms 4344 KB Output is correct
13 Correct 327 ms 4344 KB Output is correct
14 Correct 334 ms 4224 KB Output is correct
15 Correct 327 ms 4224 KB Output is correct
16 Correct 58 ms 1024 KB Output is correct
17 Correct 62 ms 1152 KB Output is correct
18 Correct 60 ms 1024 KB Output is correct
19 Correct 62 ms 1144 KB Output is correct
20 Correct 60 ms 1024 KB Output is correct
21 Correct 26 ms 3960 KB Output is correct
22 Correct 26 ms 3968 KB Output is correct
23 Correct 26 ms 3840 KB Output is correct
24 Correct 28 ms 3840 KB Output is correct
25 Correct 27 ms 3840 KB Output is correct
26 Correct 23 ms 3840 KB Output is correct
27 Correct 23 ms 3840 KB Output is correct
28 Correct 23 ms 3712 KB Output is correct
29 Correct 26 ms 3968 KB Output is correct
30 Incorrect 314 ms 4304 KB Output isn't correct
31 Halted 0 ms 0 KB -