oj.uz

Submission #406637

# Submission time Handle Problem Language Result Execution time Memory
406637 2021-05-17T22:07:22 Z gevacrt Boat (APIO16_boat) C++17
9 / 100
 2000 ms 163364 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){
    return MULT(fac(n), binexp(fac(k), MOD-2), binexp(fac(n-k), MOD-2));    
}

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 213 ms 4300 KB Output is correct
2 Correct 209 ms 4384 KB Output is correct
3 Correct 211 ms 4300 KB Output is correct
4 Correct 204 ms 4404 KB Output is correct
5 Correct 210 ms 4404 KB Output is correct
6 Correct 243 ms 4388 KB Output is correct
7 Correct 239 ms 4396 KB Output is correct
8 Correct 238 ms 4396 KB Output is correct
9 Correct 241 ms 4300 KB Output is correct
10 Correct 236 ms 4384 KB Output is correct
11 Correct 235 ms 4384 KB Output is correct
12 Correct 239 ms 4300 KB Output is correct
13 Correct 236 ms 4384 KB Output is correct
14 Correct 230 ms 4300 KB Output is correct
15 Correct 243 ms 4384 KB Output is correct
16 Correct 222 ms 4400 KB Output is correct
17 Correct 210 ms 4300 KB Output is correct
18 Correct 216 ms 4384 KB Output is correct
19 Correct 217 ms 4388 KB Output is correct
20 Correct 224 ms 4300 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4300 KB Output is correct
2 Correct 209 ms 4384 KB Output is correct
3 Correct 211 ms 4300 KB Output is correct
4 Correct 204 ms 4404 KB Output is correct
5 Correct 210 ms 4404 KB Output is correct
6 Correct 243 ms 4388 KB Output is correct
7 Correct 239 ms 4396 KB Output is correct
8 Correct 238 ms 4396 KB Output is correct
9 Correct 241 ms 4300 KB Output is correct
10 Correct 236 ms 4384 KB Output is correct
11 Correct 235 ms 4384 KB Output is correct
12 Correct 239 ms 4300 KB Output is correct
13 Correct 236 ms 4384 KB Output is correct
14 Correct 230 ms 4300 KB Output is correct
15 Correct 243 ms 4384 KB Output is correct
16 Correct 222 ms 4400 KB Output is correct
17 Correct 210 ms 4300 KB Output is correct
18 Correct 216 ms 4384 KB Output is correct
19 Correct 217 ms 4388 KB Output is correct
20 Correct 224 ms 4300 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 2101 ms 163364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 4300 KB Output is correct
2 Correct 209 ms 4384 KB Output is correct
3 Correct 211 ms 4300 KB Output is correct
4 Correct 204 ms 4404 KB Output is correct
5 Correct 210 ms 4404 KB Output is correct
6 Correct 243 ms 4388 KB Output is correct
7 Correct 239 ms 4396 KB Output is correct
8 Correct 238 ms 4396 KB Output is correct
9 Correct 241 ms 4300 KB Output is correct
10 Correct 236 ms 4384 KB Output is correct
11 Correct 235 ms 4384 KB Output is correct
12 Correct 239 ms 4300 KB Output is correct
13 Correct 236 ms 4384 KB Output is correct
14 Correct 230 ms 4300 KB Output is correct
15 Correct 243 ms 4384 KB Output is correct
16 Correct 222 ms 4400 KB Output is correct
17 Correct 210 ms 4300 KB Output is correct
18 Correct 216 ms 4384 KB Output is correct
19 Correct 217 ms 4388 KB Output is correct
20 Correct 224 ms 4300 KB Output is correct
21 Execution timed out 2076 ms 4300 KB Time limit exceeded
22 Halted 0 ms 0 KB -