oj.uz

Submission #406639

# Submission time Handle Problem Language Result Execution time Memory
406639 2021-05-17T22:17:46 Z gevacrt Boat (APIO16_boat) C++17
9 / 100
 2000 ms 4384 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define int ll

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

int MULT(){return 1;}
template<typename T, typename... Args>
int MULT(T v, Args... args){
    return (v*MULT(args...))%MOD;
}

int binexp(int base, int pow, int M=MOD){
    int res = 1;
    while(pow){
        if(pow & 1) res *= base;
        pow >>= 1, base *= base;
        if(M) base %= M, res %= M;
    }
    return res;
}
constexpr int fac(int n){
    if(n == 0) return 1;
    return MULT(n, fac(n-1));
}
int nCk(int n, int k){
    int v = binexp(fac(k), MOD-2);
    while(k--){
        v = MULT(v, n);
        n--;
    }
    return v;
}

vii A; vi B; vvi dp;

int solve(int n, int c){
    if(n == -1) return 1;
    if(c == 0) return 1;
    if(dp[n][c] != -1)
        return dp[n][c];

    auto &v = dp[n][c]; v = solve(n, c-1);

    for(int x = n, cnt = 0; x >= 0; x--){
        if(!(A[x].first <= B[c-1] and B[c] <= A[x].second))
            continue;
    
        for(int k = 0; k <= min(cnt, B[c]-B[c-1]-1); k++)
            v += MULT(nCk(B[c]-B[c-1], k+1), nCk(cnt, k), solve(x-1, c-1)), v %= MOD;

        cnt++;
    }

    return v;
}

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

    int N; cin >> N;

    A.resize(N);
    for(auto &[l, r] : A){
        cin >> l >> r; r++;    
        B.push_back(l); B.push_back(r);
    }

    sort(all(B));

    dp.resize(N, vi(B.size(), -1));
    cout << solve(N-1, B.size()-1)-1 << endl;

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 4300 KB Output is correct
2 Correct 196 ms 4380 KB Output is correct
3 Correct 212 ms 4380 KB Output is correct
4 Correct 186 ms 4376 KB Output is correct
5 Correct 194 ms 4376 KB Output is correct
6 Correct 207 ms 4300 KB Output is correct
7 Correct 202 ms 4376 KB Output is correct
8 Correct 201 ms 4300 KB Output is correct
9 Correct 217 ms 4380 KB Output is correct
10 Correct 209 ms 4372 KB Output is correct
11 Correct 213 ms 4380 KB Output is correct
12 Correct 241 ms 4300 KB Output is correct
13 Correct 201 ms 4300 KB Output is correct
14 Correct 200 ms 4376 KB Output is correct
15 Correct 207 ms 4300 KB Output is correct
16 Correct 206 ms 4376 KB Output is correct
17 Correct 193 ms 4384 KB Output is correct
18 Correct 204 ms 4372 KB Output is correct
19 Correct 193 ms 4376 KB Output is correct
20 Correct 201 ms 4376 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 4300 KB Output is correct
2 Correct 196 ms 4380 KB Output is correct
3 Correct 212 ms 4380 KB Output is correct
4 Correct 186 ms 4376 KB Output is correct
5 Correct 194 ms 4376 KB Output is correct
6 Correct 207 ms 4300 KB Output is correct
7 Correct 202 ms 4376 KB Output is correct
8 Correct 201 ms 4300 KB Output is correct
9 Correct 217 ms 4380 KB Output is correct
10 Correct 209 ms 4372 KB Output is correct
11 Correct 213 ms 4380 KB Output is correct
12 Correct 241 ms 4300 KB Output is correct
13 Correct 201 ms 4300 KB Output is correct
14 Correct 200 ms 4376 KB Output is correct
15 Correct 207 ms 4300 KB Output is correct
16 Correct 206 ms 4376 KB Output is correct
17 Correct 193 ms 4384 KB Output is correct
18 Correct 204 ms 4372 KB Output is correct
19 Correct 193 ms 4376 KB Output is correct
20 Correct 201 ms 4376 KB Output is correct
21 Execution timed out 2076 ms 4300 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 4300 KB Output is correct
2 Correct 196 ms 4380 KB Output is correct
3 Correct 212 ms 4380 KB Output is correct
4 Correct 186 ms 4376 KB Output is correct
5 Correct 194 ms 4376 KB Output is correct
6 Correct 207 ms 4300 KB Output is correct
7 Correct 202 ms 4376 KB Output is correct
8 Correct 201 ms 4300 KB Output is correct
9 Correct 217 ms 4380 KB Output is correct
10 Correct 209 ms 4372 KB Output is correct
11 Correct 213 ms 4380 KB Output is correct
12 Correct 241 ms 4300 KB Output is correct
13 Correct 201 ms 4300 KB Output is correct
14 Correct 200 ms 4376 KB Output is correct
15 Correct 207 ms 4300 KB Output is correct
16 Correct 206 ms 4376 KB Output is correct
17 Correct 193 ms 4384 KB Output is correct
18 Correct 204 ms 4372 KB Output is correct
19 Correct 193 ms 4376 KB Output is correct
20 Correct 201 ms 4376 KB Output is correct
21 Execution timed out 2076 ms 4300 KB Time limit exceeded
22 Halted 0 ms 0 KB -