oj.uz

Submission #142975

# Submission time Handle Problem Language Result Execution time Memory
142975 2019-08-12T13:16:12 Z popovicirobert Bodyguards (CEOI10_bodyguards) C++14
100 / 100
 241 ms 20204 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



/*const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;


int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    ll sum = 0;
    vector < pair <ll, ll> > r(n);
    for(auto &it : r) {
        cin >> it.first >> it.second;
        sum += it.first * it.second;
    }
    cin >> m;
    vector < pair <ll, ll> > c(m);
    for(auto &it : c) {
        cin >> it.first >> it.second;
        sum -= it.first * it.second;
    }

    if(sum != 0) {
        cout << 0;
        return 0;
    }

    sort(r.rbegin(), r.rend());
    sort(c.rbegin(), c.rend());

    vector <ll> t, spr(n), spc(m);
    for(i = 0; i < m; i++) {
        spc[i] = (i > 0 ? spc[i - 1] : 0) + c[i].first * c[i].second;
        c[i].second += (i > 0 ? c[i - 1].second : 0);
        t.push_back(c[i].second);
    }
    for(i = 0; i < n; i++) {
        spr[i] = (i > 0 ? spr[i - 1] : 0) + r[i].first * r[i].second;
        r[i].second += (i > 0 ? r[i - 1].second : 0);
        if(r[i].second <= c.back().second)
            t.push_back(r[i].second);
    }
    sort(t.begin(), t.end());

    auto get = [&](ll k) {
        int res = -1;
        for(int step = 1 << 17; step; step >>= 1) {
            if(res + step < m && c[res + step].second < k) {
                res += step;
            }
        }
        ll last = (res >= 0 ? c[res].second : 0);
        return (res >= 0 ? spc[res] : 0) + (k - last) * c[res + 1].first;
    };

    int p = n - 1;
    for(auto k : t) {
        while(p >= 0 && r[p].first <= k) {
            p--;
        }
        ll sumr = k * (p >= 0 ? r[p].second : 0) + spr[n - 1] - (p >= 0 ? spr[p] : 0);
        ll sumc = get(k);
        if(sumr < sumc) {
            cout << 0;
            return 0;
        }
    }

    cout << 1;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 0 ms 248 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 380 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 3 ms 424 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 4 ms 504 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 412 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct
2 Correct 4 ms 572 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 7 ms 1012 KB Output is correct
11 Correct 6 ms 888 KB Output is correct
12 Correct 6 ms 888 KB Output is correct
13 Correct 6 ms 888 KB Output is correct
14 Correct 7 ms 888 KB Output is correct
15 Correct 7 ms 1016 KB Output is correct
16 Correct 7 ms 888 KB Output is correct
17 Correct 7 ms 888 KB Output is correct
18 Correct 7 ms 888 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4084 KB Output is correct
2 Correct 22 ms 2808 KB Output is correct
3 Correct 39 ms 4596 KB Output is correct
4 Correct 50 ms 4596 KB Output is correct
5 Correct 43 ms 4796 KB Output is correct
6 Correct 44 ms 5236 KB Output is correct
7 Correct 36 ms 4084 KB Output is correct
8 Correct 42 ms 5236 KB Output is correct
9 Correct 40 ms 4980 KB Output is correct
10 Correct 48 ms 5080 KB Output is correct
11 Correct 40 ms 4984 KB Output is correct
12 Correct 53 ms 5236 KB Output is correct
13 Correct 40 ms 4976 KB Output is correct
14 Correct 51 ms 5236 KB Output is correct
15 Correct 52 ms 5236 KB Output is correct
16 Correct 52 ms 5108 KB Output is correct
17 Correct 51 ms 5236 KB Output is correct
18 Correct 47 ms 5016 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6104 KB Output is correct
2 Correct 53 ms 6440 KB Output is correct
3 Correct 103 ms 9200 KB Output is correct
4 Correct 15 ms 1784 KB Output is correct
5 Correct 104 ms 10096 KB Output is correct
6 Correct 68 ms 7412 KB Output is correct
7 Correct 88 ms 9500 KB Output is correct
8 Correct 12 ms 1424 KB Output is correct
9 Correct 112 ms 10096 KB Output is correct
10 Correct 79 ms 9536 KB Output is correct
11 Correct 78 ms 9456 KB Output is correct
12 Correct 79 ms 9516 KB Output is correct
13 Correct 112 ms 9968 KB Output is correct
14 Correct 112 ms 9968 KB Output is correct
15 Correct 110 ms 9844 KB Output is correct
16 Correct 112 ms 9876 KB Output is correct
17 Correct 119 ms 9772 KB Output is correct
18 Correct 116 ms 9800 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 12404 KB Output is correct
2 Correct 152 ms 12364 KB Output is correct
3 Correct 109 ms 9484 KB Output is correct
4 Correct 48 ms 4856 KB Output is correct
5 Correct 165 ms 16108 KB Output is correct
6 Correct 208 ms 20204 KB Output is correct
7 Correct 121 ms 11020 KB Output is correct
8 Correct 137 ms 13688 KB Output is correct
9 Correct 159 ms 18472 KB Output is correct
10 Correct 158 ms 18412 KB Output is correct
11 Correct 159 ms 18360 KB Output is correct
12 Correct 160 ms 18372 KB Output is correct
13 Correct 159 ms 18380 KB Output is correct
14 Correct 18 ms 2424 KB Output is correct
15 Correct 241 ms 19564 KB Output is correct
16 Correct 238 ms 19564 KB Output is correct
17 Correct 241 ms 19692 KB Output is correct
18 Correct 209 ms 18540 KB Output is correct