oj.uz

Submission #315983

# Submission time Handle Problem Language Result Execution time Memory
315983 2020-10-24T16:40:45 Z phathnv Boat (APIO16_boat) C++11
0 / 100
 6 ms 4480 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 = 501;
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 = 0; j < nX; j++){
            int len = x[j + 1] - x[j];
            for(int k = 0; 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[i][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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 4480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -