oj.uz

Submission #23338

# Submission time Handle Problem Language Result Execution time Memory
23338 2017-05-06T10:55:30 Z duongthoi1999 Boat (APIO16_boat) C++14
9 / 100
 2000 ms 10084 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
typedef pair<ll, int> ii;
const int mod = (int) 1e9 + 7;
const ll inf = 1LL << 60;
const int maxn = (int) 1005;
const ld eps = 1e-9;

void add(int &a, ll b) {
    a += (b % mod);
    while (a >= mod) a -= mod;
}

ll pw(ll a, int b) {
    ll res = 1;
    while (b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int n, m, a[maxn], b[maxn], sz[maxn];
int f[maxn][maxn], C[maxn][maxn];
vector<int> p;

int test(int N) {
    C[0][0] = 1;
    rep(i, 1, N + 1) {
        C[i][0] = 1;
        rep(j, 1, N + 1) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
    rep(i, 1, N + 1) {
        int res = 0;
        rep(j, 1, i + 1) res += C[N][j] * C[i - 1][j - 1];
        cout << i << ": " << res << endl;
    }
}

int main() {
//    test(6);
//    return 0;
    //freopen("test.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    rep(i, 1, n + 1) {
        cin >> a[i] >> b[i];
        b[i] ++;
        p.pb(a[i]);
        p.pb(b[i]);
    }
    p.pb(0);
    sort(all(p));
    p.resize(unique(all(p)) - p.begin());
    rep(i, 1, n + 1) a[i] = lower_bound(all(p), a[i]) - p.begin();
    rep(i, 1, n + 1) b[i] = lower_bound(all(p), b[i]) - p.begin();
    m = SZ(p) - 2;
    rep(i, 1, m + 1) sz[i] = p[i + 1] - p[i];
    rep(i, 0, m + 1) f[0][i] = 1;
    rep(i, 1, n + 1) {
        rep(k, a[i], b[i]) {
            ll cnt = 1, x = sz[k], y = 1;
            per(j, 0, i) {
                cnt = (cnt * x % mod) * pw(y, mod - 2) % mod;
                x ++, y ++;
                add(f[i][k], cnt * f[j][k - 1]);
            }
        }
        rep(j, 1, m + 1) f[i][j] += f[i][j - 1];
    }
//    rep(i, 1, n + 1) {
//        rep(j, 1, m + 1) cout << f[i][j] << ' ';
//        cout << endl;
//    }
    int ans = 0;
    rep(i, 1, n + 1) add(ans, f[i][m]);
    cout << ans << endl;
}

Compilation message

boat.cpp: In function 'int test(int)':
boat.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10084 KB Output is correct
2 Correct 29 ms 10084 KB Output is correct
3 Correct 23 ms 10084 KB Output is correct
4 Correct 29 ms 10084 KB Output is correct
5 Correct 26 ms 10084 KB Output is correct
6 Correct 29 ms 10084 KB Output is correct
7 Correct 29 ms 10084 KB Output is correct
8 Correct 29 ms 10084 KB Output is correct
9 Correct 26 ms 10084 KB Output is correct
10 Correct 29 ms 10084 KB Output is correct
11 Correct 33 ms 10084 KB Output is correct
12 Correct 29 ms 10084 KB Output is correct
13 Correct 29 ms 10084 KB Output is correct
14 Correct 29 ms 10084 KB Output is correct
15 Correct 23 ms 10084 KB Output is correct
16 Correct 29 ms 10084 KB Output is correct
17 Correct 23 ms 10084 KB Output is correct
18 Correct 26 ms 10084 KB Output is correct
19 Correct 26 ms 10084 KB Output is correct
20 Correct 26 ms 10084 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10084 KB Output is correct
2 Correct 29 ms 10084 KB Output is correct
3 Correct 23 ms 10084 KB Output is correct
4 Correct 29 ms 10084 KB Output is correct
5 Correct 26 ms 10084 KB Output is correct
6 Correct 29 ms 10084 KB Output is correct
7 Correct 29 ms 10084 KB Output is correct
8 Correct 29 ms 10084 KB Output is correct
9 Correct 26 ms 10084 KB Output is correct
10 Correct 29 ms 10084 KB Output is correct
11 Correct 33 ms 10084 KB Output is correct
12 Correct 29 ms 10084 KB Output is correct
13 Correct 29 ms 10084 KB Output is correct
14 Correct 29 ms 10084 KB Output is correct
15 Correct 23 ms 10084 KB Output is correct
16 Correct 29 ms 10084 KB Output is correct
17 Correct 23 ms 10084 KB Output is correct
18 Correct 26 ms 10084 KB Output is correct
19 Correct 26 ms 10084 KB Output is correct
20 Correct 26 ms 10084 KB Output is correct
21 Execution timed out 2000 ms 10084 KB Execution timed out
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10084 KB Output is correct
2 Correct 29 ms 10084 KB Output is correct
3 Correct 23 ms 10084 KB Output is correct
4 Correct 29 ms 10084 KB Output is correct
5 Correct 26 ms 10084 KB Output is correct
6 Correct 29 ms 10084 KB Output is correct
7 Correct 29 ms 10084 KB Output is correct
8 Correct 29 ms 10084 KB Output is correct
9 Correct 26 ms 10084 KB Output is correct
10 Correct 29 ms 10084 KB Output is correct
11 Correct 33 ms 10084 KB Output is correct
12 Correct 29 ms 10084 KB Output is correct
13 Correct 29 ms 10084 KB Output is correct
14 Correct 29 ms 10084 KB Output is correct
15 Correct 23 ms 10084 KB Output is correct
16 Correct 29 ms 10084 KB Output is correct
17 Correct 23 ms 10084 KB Output is correct
18 Correct 26 ms 10084 KB Output is correct
19 Correct 26 ms 10084 KB Output is correct
20 Correct 26 ms 10084 KB Output is correct
21 Execution timed out 2000 ms 10084 KB Execution timed out
22 Halted 0 ms 0 KB -