oj.uz

Submission #722272

# Submission time Handle Problem Language Result Execution time Memory
722272 2023-04-11T16:37:23 Z Dec0Dedd Bodyguards (CEOI10_bodyguards) C++14
0 / 100
 92 ms 14232 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]={};

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

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

        int l=0, r=sz-1, 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 (pc[res+1] < 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;
    for (int i=1; i<=r; ++i) {
        ll x, val; cin>>val>>x;
        vr.push_back({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});
    } sort(vc.begin(), vc.end(), greater<pii>());

    cout<<solve(vr, vc)<<"\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 3580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 7960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 14232 KB Output is correct
2 Correct 89 ms 14060 KB Output is correct
3 Correct 84 ms 12624 KB Output is correct
4 Incorrect 29 ms 5196 KB Output isn't correct
5 Halted 0 ms 0 KB -