oj.uz

Submission #230102

# Submission time Handle Problem Language Result Execution time Memory
230102 2020-05-08T09:39:25 Z lyc Boat (APIO16_boat) C++14
9 / 100
 1549 ms 7676 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 505;
const int MOD = 1e9+7;

int N, A[MX_N], B[MX_N];
vector<int> val;

int dp[MX_N][2*MX_N];
int pre[MX_N][2*MX_N];

int inv[MX_N];
map<int,vector<int>> nck;
map<int,vector<int>> prod;

void precomp(int n) {
    if (nck.count(n)) return;
    auto& v = nck[n];
    v.assign(N+1,1);
    FOR(k,1,N) v[k] = 1LL * v[k-1] * (n-k+1) % MOD * inv[k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){
        cin >> A[i] >> B[i];
        B[i] += 1;
        val.push_back(A[i]);
        val.push_back(B[i]);
    }
    sort(ALL(val));
    val.resize(unique(ALL(val))-val.begin());
    FOR(i,1,N){
        A[i] = lower_bound(ALL(val),A[i])-val.begin();
        B[i] = lower_bound(ALL(val),B[i])-val.begin();
    }

    inv[1] = 1;
    FOR(i,2,N) inv[i] = (MOD - 1LL * (MOD/i) * inv[MOD%i] % MOD) % MOD;
    FOR(i,0,N) precomp(i);
    FOR(i,1,SZ(val)-1) precomp(val[i]-val[i-1]);
    FOR(i,1,SZ(val)-1){
        precomp(val[i]-val[i-1]);
        auto& u = nck[val[i]-val[i-1]];
        auto& v = prod[val[i]-val[i-1]];
        v.assign(N+1,0);
        FOR(x,0,N-2){
            auto& w = nck[x];
            FOR(k,0,x){
                v[x] += 1LL * u[k+2] * w[k] % MOD;
                v[x] %= MOD;
            }
        }
    }

        RFOR(x,SZ(val)-1,0){
            dp[N+1][x] = 1;
            pre[N+1][x] = dp[N+1][x];
        }
    RFOR(i,N,1){
        RFOR(x,SZ(val)-1,0){
            dp[i][x] = 0;
            if (x+1 < SZ(val)) dp[i][x] = (dp[i][x] + dp[i][x+1]) % MOD;
            if (A[i] <= x && x < B[i]) {
                FOR(j,i,N){
                    if (A[i] > x || B[i] <= x) break;
                    int coeff = 0;
                    if (i == j) {
                        coeff = val[x+1]-val[x];
                    } else {
                        coeff = prod[val[x+1]-val[x]][j-i-1];
                    }
                    int sum = (pre[j+1][x+1] - pre[N+2][x+1] + MOD) % MOD;
                    dp[i][x] = (dp[i][x] + 1LL * coeff * sum % MOD) % MOD;
                }
            }
            pre[i][x] = (pre[i+1][x] + dp[i][x]) % MOD;
            //TRACE(i _ x _ dp[i][x]);
        }
    }

    int ans = 0;
    FOR(i,1,N){
        ans = (ans + dp[i][0]) % MOD;
    }
    cout << ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 7560 KB Output is correct
2 Correct 1190 ms 7400 KB Output is correct
3 Correct 1188 ms 7540 KB Output is correct
4 Correct 1188 ms 7416 KB Output is correct
5 Correct 1198 ms 7628 KB Output is correct
6 Correct 1210 ms 7440 KB Output is correct
7 Correct 1212 ms 7416 KB Output is correct
8 Correct 1203 ms 7672 KB Output is correct
9 Correct 1200 ms 7416 KB Output is correct
10 Correct 1197 ms 7568 KB Output is correct
11 Correct 1204 ms 7416 KB Output is correct
12 Correct 1195 ms 7572 KB Output is correct
13 Correct 1196 ms 7676 KB Output is correct
14 Correct 1195 ms 7420 KB Output is correct
15 Correct 1194 ms 7508 KB Output is correct
16 Correct 220 ms 5880 KB Output is correct
17 Correct 238 ms 5752 KB Output is correct
18 Correct 232 ms 5772 KB Output is correct
19 Correct 236 ms 5880 KB Output is correct
20 Correct 231 ms 5788 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 7560 KB Output is correct
2 Correct 1190 ms 7400 KB Output is correct
3 Correct 1188 ms 7540 KB Output is correct
4 Correct 1188 ms 7416 KB Output is correct
5 Correct 1198 ms 7628 KB Output is correct
6 Correct 1210 ms 7440 KB Output is correct
7 Correct 1212 ms 7416 KB Output is correct
8 Correct 1203 ms 7672 KB Output is correct
9 Correct 1200 ms 7416 KB Output is correct
10 Correct 1197 ms 7568 KB Output is correct
11 Correct 1204 ms 7416 KB Output is correct
12 Correct 1195 ms 7572 KB Output is correct
13 Correct 1196 ms 7676 KB Output is correct
14 Correct 1195 ms 7420 KB Output is correct
15 Correct 1194 ms 7508 KB Output is correct
16 Correct 220 ms 5880 KB Output is correct
17 Correct 238 ms 5752 KB Output is correct
18 Correct 232 ms 5772 KB Output is correct
19 Correct 236 ms 5880 KB Output is correct
20 Correct 231 ms 5788 KB Output is correct
21 Incorrect 1549 ms 5456 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1190 ms 7560 KB Output is correct
2 Correct 1190 ms 7400 KB Output is correct
3 Correct 1188 ms 7540 KB Output is correct
4 Correct 1188 ms 7416 KB Output is correct
5 Correct 1198 ms 7628 KB Output is correct
6 Correct 1210 ms 7440 KB Output is correct
7 Correct 1212 ms 7416 KB Output is correct
8 Correct 1203 ms 7672 KB Output is correct
9 Correct 1200 ms 7416 KB Output is correct
10 Correct 1197 ms 7568 KB Output is correct
11 Correct 1204 ms 7416 KB Output is correct
12 Correct 1195 ms 7572 KB Output is correct
13 Correct 1196 ms 7676 KB Output is correct
14 Correct 1195 ms 7420 KB Output is correct
15 Correct 1194 ms 7508 KB Output is correct
16 Correct 220 ms 5880 KB Output is correct
17 Correct 238 ms 5752 KB Output is correct
18 Correct 232 ms 5772 KB Output is correct
19 Correct 236 ms 5880 KB Output is correct
20 Correct 231 ms 5788 KB Output is correct
21 Incorrect 1549 ms 5456 KB Output isn't correct
22 Halted 0 ms 0 KB -