oj.uz

Submission #136899

# Submission time Handle Problem Language Result Execution time Memory
136899 2019-07-26T13:39:31 Z choikiwon Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 169 ms 13028 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int R, C;
vector<pii> X, Y;
vector<ll> csum;
vector<ll> psum;

ll f(ll k) {
    int s = 0, e = (int)Y.size() - 1, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(Y[m].first >= k) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }

    ll ret = psum.back();
    if(p != -1) {
        ret += csum[p] * k;
        ret -= psum[p];
    }
    return ret;
}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> R;

    for(int i = 0; i < R; i++) {
        int a, b; cin >> a >> b;

        X.push_back(pii(a, b));
    }

    cin >> C;

    for(int i = 0; i < C; i++) {
        int a, b; cin >> a >> b;

        Y.push_back(pii(a, b));
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    reverse(X.begin(), X.end());
    reverse(Y.begin(), Y.end());

    csum.resize(Y.size());
    psum.resize(Y.size());
    for(int i = 0; i < Y.size(); i++) {
        csum[i] = Y[i].second;
        psum[i] = 1LL * Y[i].first * Y[i].second;
        if(i) {
            csum[i] += csum[i - 1];
            psum[i] += psum[i - 1];
        }
    }

    ll sum = 0;
    ll k = 0;
    for(int i = 0; i < X.size(); i++) {
        sum += 1LL * X[i].first * X[i].second;
        k += X[i].second;

        if(sum > f(k)) {
            cout << 0;
            return 0;
        }
    }
    cout << 1;
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < Y.size(); i++) {
                    ~~^~~~~~~~~~
bodyguards.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); i++) {
                    ~~^~~~~~~~~~

Subtask #1
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 504 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 380 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 380 KB Output is correct
17 Correct 2 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 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 2 ms 380 KB Output is correct
10 Correct 2 ms 380 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 380 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 352 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 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 4 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 248 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #5
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 3 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 3 ms 376 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 2 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 2 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 380 KB Output is correct
18 Correct 3 ms 376 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 376 KB Output is correct
4 Correct 2 ms 296 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 376 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 632 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 676 KB Output is correct
10 Correct 6 ms 676 KB Output is correct
11 Correct 6 ms 632 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 6 ms 632 KB Output is correct
14 Correct 6 ms 632 KB Output is correct
15 Correct 6 ms 632 KB Output is correct
16 Correct 6 ms 632 KB Output is correct
17 Correct 6 ms 632 KB Output is correct
18 Correct 6 ms 632 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2292 KB Output is correct
2 Correct 21 ms 2164 KB Output is correct
3 Correct 34 ms 3004 KB Output is correct
4 Correct 35 ms 2804 KB Output is correct
5 Correct 35 ms 2804 KB Output is correct
6 Correct 40 ms 3572 KB Output is correct
7 Correct 30 ms 2264 KB Output is correct
8 Correct 41 ms 3712 KB Output is correct
9 Correct 36 ms 3312 KB Output is correct
10 Correct 36 ms 3316 KB Output is correct
11 Correct 41 ms 3448 KB Output is correct
12 Correct 38 ms 3444 KB Output is correct
13 Correct 37 ms 3316 KB Output is correct
14 Correct 39 ms 3440 KB Output is correct
15 Correct 39 ms 3436 KB Output is correct
16 Correct 39 ms 3440 KB Output is correct
17 Correct 39 ms 3316 KB Output is correct
18 Correct 38 ms 3316 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5104 KB Output is correct
2 Correct 53 ms 4372 KB Output is correct
3 Correct 72 ms 5740 KB Output is correct
4 Correct 12 ms 1272 KB Output is correct
5 Correct 81 ms 6508 KB Output is correct
6 Correct 64 ms 5104 KB Output is correct
7 Correct 75 ms 6040 KB Output is correct
8 Correct 11 ms 1268 KB Output is correct
9 Correct 76 ms 6508 KB Output is correct
10 Correct 70 ms 6124 KB Output is correct
11 Correct 72 ms 6216 KB Output is correct
12 Correct 71 ms 6252 KB Output is correct
13 Correct 75 ms 6384 KB Output is correct
14 Correct 78 ms 6268 KB Output is correct
15 Correct 77 ms 6228 KB Output is correct
16 Correct 76 ms 6276 KB Output is correct
17 Correct 77 ms 6200 KB Output is correct
18 Correct 77 ms 6248 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 8680 KB Output is correct
2 Correct 108 ms 8640 KB Output is correct
3 Correct 97 ms 7916 KB Output is correct
4 Correct 40 ms 3800 KB Output is correct
5 Correct 126 ms 9288 KB Output is correct
6 Correct 130 ms 13028 KB Output is correct
7 Correct 90 ms 7232 KB Output is correct
8 Correct 114 ms 9552 KB Output is correct
9 Correct 139 ms 11856 KB Output is correct
10 Correct 138 ms 11820 KB Output is correct
11 Correct 138 ms 11720 KB Output is correct
12 Correct 139 ms 11748 KB Output is correct
13 Correct 140 ms 11772 KB Output is correct
14 Correct 17 ms 1652 KB Output is correct
15 Correct 164 ms 12388 KB Output is correct
16 Correct 164 ms 12260 KB Output is correct
17 Correct 169 ms 12272 KB Output is correct
18 Correct 149 ms 11748 KB Output is correct