oj.uz

Submission #722282

# Submission time Handle Problem Language Result Execution time Memory
722282 2023-04-11T17:07:46 Z Dec0Dedd Bodyguards (CEOI10_bodyguards) C++14
90 / 100
 92 ms 16304 KB 
#include <bits/stdc++.h>

using namespace std;

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

const ll INF = 1e9+10;

ll r, c;

int solve(vector<pii> vr, vector<pii> vc) {
    ll sz=vc.size(), pc[sz+10]={}, pcnt[sz+10]={};

    for (int i=0; i<sz; ++i) pc[i+1]=pc[i]+vc[i].first*vc[i].second;
    for (int i=0; i<sz; ++i) pcnt[i+1]=pcnt[i]+vc[i].second;

    ll sm=0, cnt=0, ls=0;
    for (auto u : vc) ls+=u.first*u.second;

    for (auto u : vr) {
        sm+=u.first*u.second, cnt+=u.second;

        int l=0, r=sz, res=sz-1;
        while (l <= r) {
            int m=(l+r)/2;
            if (vc[m].first >= cnt) l=m+1, res=m;
            else r=m-1;
        }
        if (vc[res].first < cnt) --res;

        ll g=1ll*pcnt[res+1]*cnt+(ls-pc[res+1]);
        if (g < sm) return false;
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<pii> vr, vc;
    cin>>r;

    ll rsm=0, csm=0;
    for (int i=1; i<=r; ++i) {
        ll x, val; cin>>val>>x;
        vr.push_back({val, x});
        rsm+=val*x;   
    } sort(vr.begin(), vr.end(), greater<pii>());

    cin>>c;
    for (int i=1; i<=c; ++i) {
        ll x, val; cin>>val>>x;
        vc.push_back({val, x});
        csm+=val*x;
    } sort(vc.begin(), vc.end(), greater<pii>());

    if (rsm != csm) cout<<0<<"\n";
    else cout<<solve(vr, vc)<<"\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 224 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 324 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 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 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 0 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 336 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 #5
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 332 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 324 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 332 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 2 ms 344 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 456 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 3 ms 848 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 4 ms 840 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 3 ms 852 KB Output is correct
13 Correct 5 ms 836 KB Output is correct
14 Correct 4 ms 852 KB Output is correct
15 Correct 3 ms 804 KB Output is correct
16 Correct 3 ms 800 KB Output is correct
17 Correct 3 ms 852 KB Output is correct
18 Correct 3 ms 824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2888 KB Output is correct
2 Correct 18 ms 3116 KB Output is correct
3 Correct 24 ms 4908 KB Output is correct
4 Correct 27 ms 4664 KB Output is correct
5 Correct 28 ms 4724 KB Output is correct
6 Correct 29 ms 5672 KB Output is correct
7 Correct 21 ms 3856 KB Output is correct
8 Correct 31 ms 5716 KB Output is correct
9 Correct 28 ms 5464 KB Output is correct
10 Correct 28 ms 5440 KB Output is correct
11 Correct 24 ms 5452 KB Output is correct
12 Correct 29 ms 5664 KB Output is correct
13 Correct 26 ms 5344 KB Output is correct
14 Correct 28 ms 5684 KB Output is correct
15 Correct 27 ms 5640 KB Output is correct
16 Correct 29 ms 5584 KB Output is correct
17 Correct 30 ms 5596 KB Output is correct
18 Correct 26 ms 5400 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 6464 KB Output is correct
2 Correct 43 ms 7248 KB Output is correct
3 Correct 56 ms 9872 KB Output is correct
4 Correct 8 ms 1872 KB Output is correct
5 Correct 77 ms 11048 KB Output is correct
6 Correct 50 ms 8736 KB Output is correct
7 Correct 60 ms 10144 KB Output is correct
8 Correct 7 ms 1748 KB Output is correct
9 Correct 72 ms 11012 KB Output is correct
10 Correct 54 ms 10404 KB Output is correct
11 Correct 50 ms 10312 KB Output is correct
12 Correct 52 ms 10392 KB Output is correct
13 Correct 68 ms 11036 KB Output is correct
14 Correct 56 ms 10804 KB Output is correct
15 Correct 56 ms 10808 KB Output is correct
16 Correct 58 ms 10948 KB Output is correct
17 Correct 58 ms 10820 KB Output is correct
18 Correct 57 ms 10804 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 11244 KB Output is correct
2 Correct 74 ms 11048 KB Output is correct
3 Correct 76 ms 10168 KB Output is correct
4 Correct 29 ms 4364 KB Output is correct
5 Incorrect 92 ms 16304 KB Output isn't correct
6 Halted 0 ms 0 KB -