oj.uz

Submission #440661

# Submission time Handle Problem Language Result Execution time Memory
440661 2021-07-02T16:43:40 Z prvocislo Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 195 ms 17080 KB 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<ll> v(1, 0); // pocty riadkov po ktorych sa musime pozriet na to ako sa funkcia vyvyja
    int r;
    cin >> r;
    vector<pair<ll, ll> > vr(r); // {dlzka, pocet} -> pocet bude postupne stupat
    for (int i = 0; i < r; i++) cin >> vr[i].first >> vr[i].second;
    sort(vr.begin(), vr.end(), greater<pair<ll, ll> > ());
    for (int i = 0; i < r; i++)
    {
        if (i) vr[i].second += vr[i-1].second;
        v.push_back(vr[i].second);
    }
    int c;
    cin >> c;
    vector<pair<ll, ll> > vc(c); // {dlzka, pocet} -> pocet bude postupne klesat
    for (int i = 0; i < c; i++) cin >> vc[i].first >> vc[i].second;
    sort(vc.begin(), vc.end());
    for (int i = c - 1; i >= 0; i--)
    {
        if (i < c - 1) vc[i].second += vc[i+1].second;
        v.push_back(vc[i].first);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    ll delta = 0, ir = 0, ic = 0;
    for (int i = 1; i < v.size(); i++)
    {
        ll cnt = v[i] - v[i-1];
        while (ir < r && vr[ir].second < v[i]) ir++;
        ll cr = vr[ir].first * cnt; // kolko bodyguardov chcu mat nove riadky
        while (ic < c && vc[ic].first < v[i]) ic++; // kym mame prilis malu vysku
        ll cc = 0;
        if (ic < c) cc = vc[ic].second * cnt; // kolko bodyguardov maju nove stlpce
        delta += cc - cr;
        if (delta < 0)
        {
            cout << "0\n";
            return 0;
        }
    }
    cout << "1\n";
    return 0;
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 1; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 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 320 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3356 KB Output is correct
2 Correct 20 ms 2384 KB Output is correct
3 Correct 37 ms 3760 KB Output is correct
4 Correct 35 ms 3780 KB Output is correct
5 Correct 35 ms 3828 KB Output is correct
6 Correct 42 ms 4336 KB Output is correct
7 Correct 29 ms 3404 KB Output is correct
8 Correct 43 ms 4468 KB Output is correct
9 Correct 41 ms 4252 KB Output is correct
10 Correct 37 ms 4236 KB Output is correct
11 Correct 38 ms 4244 KB Output is correct
12 Correct 41 ms 4448 KB Output is correct
13 Correct 36 ms 4280 KB Output is correct
14 Correct 41 ms 4292 KB Output is correct
15 Correct 42 ms 4296 KB Output is correct
16 Correct 42 ms 4296 KB Output is correct
17 Correct 41 ms 4288 KB Output is correct
18 Correct 37 ms 4164 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 7060 KB Output is correct
2 Correct 57 ms 5284 KB Output is correct
3 Correct 76 ms 7688 KB Output is correct
4 Correct 14 ms 1440 KB Output is correct
5 Correct 90 ms 8528 KB Output is correct
6 Correct 69 ms 7084 KB Output is correct
7 Correct 80 ms 7876 KB Output is correct
8 Correct 10 ms 1400 KB Output is correct
9 Correct 84 ms 8316 KB Output is correct
10 Correct 77 ms 8000 KB Output is correct
11 Correct 77 ms 8000 KB Output is correct
12 Correct 80 ms 7980 KB Output is correct
13 Correct 83 ms 8384 KB Output is correct
14 Correct 80 ms 8124 KB Output is correct
15 Correct 81 ms 8132 KB Output is correct
16 Correct 79 ms 8120 KB Output is correct
17 Correct 79 ms 8132 KB Output is correct
18 Correct 83 ms 8128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 13080 KB Output is correct
2 Correct 119 ms 12860 KB Output is correct
3 Correct 114 ms 9792 KB Output is correct
4 Correct 37 ms 4400 KB Output is correct
5 Correct 132 ms 13596 KB Output is correct
6 Correct 110 ms 17080 KB Output is correct
7 Correct 93 ms 9084 KB Output is correct
8 Correct 155 ms 13356 KB Output is correct
9 Correct 152 ms 15552 KB Output is correct
10 Correct 151 ms 15548 KB Output is correct
11 Correct 164 ms 15496 KB Output is correct
12 Correct 155 ms 15544 KB Output is correct
13 Correct 153 ms 15544 KB Output is correct
14 Correct 15 ms 2000 KB Output is correct
15 Correct 195 ms 16340 KB Output is correct
16 Correct 176 ms 16236 KB Output is correct
17 Correct 182 ms 16336 KB Output is correct
18 Correct 157 ms 15932 KB Output is correct