oj.uz

Submission #778949

# Submission time Handle Problem Language Result Execution time Memory
778949 2023-07-11T04:40:55 Z 이성호(#10001) Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 107 ms 18304 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#define int long long
using namespace std;
pair<int, int> a[200005];
pair<int, int> b[200005];
int R, C;
int prfb[200005];
int sum[200005];
int cnt[200005];
int sufcnt[200005];
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> R;
    for (int i = 1; i <= R; i++) cin >> a[i].first >> a[i].second;
    cin >> C;
    for (int i = 1; i <= C; i++) cin >> b[i].first >> b[i].second;
    int suma = 0, sumb = 0;
    for (int i = 1; i <= R; i++) suma += a[i].first * a[i].second;
    for (int i = 1; i <= C; i++) sumb += b[i].first * b[i].second;
    if (suma != sumb) {
        cout << 0 << '\n';
        return 0;
    }
    sort(b + 1, b + C + 1); reverse(b + 1, b + C + 1);
    for (int i = 1; i <= C; i++) prfb[i] = prfb[i-1] + b[i].second;
    for (int i = 1; i <= R; i++) {
        int id = lower_bound(prfb + 1, prfb + C + 1, a[i].first) - prfb - 1;
        sum[id] += a[i].first * a[i].second;
        cnt[id] += a[i].second;
    }
    for (int i = C + 1; i >= 0; i--) sufcnt[i] = sufcnt[i+1] + cnt[i];
    int lft = b[1].first * b[1].second;
    int rht = 0;
    for (int i = 1; i <= R; i++) rht += min(a[i].first, b[1].second) * a[i].second;
    bool ok = lft <= rht;
    for (int i = 2; i <= C; i++) {
        lft += b[i].first * b[i].second;
        rht += sufcnt[i] * b[i].second + sum[i-1] - cnt[i-1] * prfb[i-1];
        ok &= lft <= rht;
    }
    cout << ok << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 708 KB Output is correct
7 Correct 2 ms 804 KB Output is correct
8 Correct 2 ms 704 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 3 ms 720 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 2 ms 724 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Correct 2 ms 724 KB Output is correct
18 Correct 2 ms 724 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3192 KB Output is correct
2 Correct 11 ms 2424 KB Output is correct
3 Correct 19 ms 4308 KB Output is correct
4 Correct 18 ms 3772 KB Output is correct
5 Correct 19 ms 3800 KB Output is correct
6 Correct 23 ms 4784 KB Output is correct
7 Correct 15 ms 3144 KB Output is correct
8 Correct 28 ms 4820 KB Output is correct
9 Correct 22 ms 4684 KB Output is correct
10 Correct 22 ms 4680 KB Output is correct
11 Correct 23 ms 4676 KB Output is correct
12 Correct 22 ms 4756 KB Output is correct
13 Correct 21 ms 4684 KB Output is correct
14 Correct 21 ms 4076 KB Output is correct
15 Correct 21 ms 4040 KB Output is correct
16 Correct 20 ms 4080 KB Output is correct
17 Correct 25 ms 4080 KB Output is correct
18 Correct 21 ms 4688 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7260 KB Output is correct
2 Correct 36 ms 6160 KB Output is correct
3 Correct 46 ms 8332 KB Output is correct
4 Correct 6 ms 1480 KB Output is correct
5 Correct 50 ms 9312 KB Output is correct
6 Correct 36 ms 7372 KB Output is correct
7 Correct 43 ms 8556 KB Output is correct
8 Correct 6 ms 1364 KB Output is correct
9 Correct 47 ms 9336 KB Output is correct
10 Correct 43 ms 8948 KB Output is correct
11 Correct 45 ms 8940 KB Output is correct
12 Correct 43 ms 9020 KB Output is correct
13 Correct 51 ms 9296 KB Output is correct
14 Correct 43 ms 7756 KB Output is correct
15 Correct 43 ms 7788 KB Output is correct
16 Correct 42 ms 7756 KB Output is correct
17 Correct 43 ms 7688 KB Output is correct
18 Correct 42 ms 7800 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 12396 KB Output is correct
2 Correct 69 ms 12248 KB Output is correct
3 Correct 56 ms 11616 KB Output is correct
4 Correct 22 ms 4528 KB Output is correct
5 Correct 72 ms 13276 KB Output is correct
6 Correct 77 ms 15920 KB Output is correct
7 Correct 52 ms 9804 KB Output is correct
8 Correct 67 ms 14172 KB Output is correct
9 Correct 102 ms 17552 KB Output is correct
10 Correct 90 ms 17564 KB Output is correct
11 Correct 97 ms 17564 KB Output is correct
12 Correct 87 ms 17536 KB Output is correct
13 Correct 98 ms 17496 KB Output is correct
14 Correct 8 ms 2132 KB Output is correct
15 Correct 96 ms 18280 KB Output is correct
16 Correct 100 ms 18304 KB Output is correct
17 Correct 107 ms 18256 KB Output is correct
18 Correct 96 ms 17520 KB Output is correct