Submission #1322972

#TimeUsernameProblemLanguageResultExecution timeMemory
1322972syanvuBodyguards (CEOI10_bodyguards)C++20
100 / 100
83 ms6680 KiB
// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define int long long
#define all(v) v.begin(),v.end()
using namespace std;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e4 + 1, MX = 40, inf = 1e18;

void solve(){
    int n;
    cin >> n;
    pair<int, int> r[n + 1];
    int sumr = 0, sumc = 0, br = 0, bc = 0;
    for(int i = 1; i <= n; i++){
        cin >> r[i].first >> r[i].second;
        sumr += r[i].second;
        br += r[i].first * r[i].second;
    }
    int m;
    cin >> m;
    pair<int, int> c[m + 1];
    for(int i = 1; i <= m; i++){
        cin >> c[i].first >> c[i].second;
        sumc += c[i].second;
        bc += c[i].first * c[i].second;
    }
    if(br != bc){
        cout << 0 << '\n';
        return;
    }
    sort(r + 1, r + n + 1);
    sort(c + 1, c + m + 1);
    if(sumc < r[n].first){
        cout << 0 << '\n';
        return;
    }
    if(sumr < c[m].first){
        cout << 0 << '\n';
        return;
    }
    reverse(r + 1, r + n + 1);
    int j = 0, cur = 0, curc = 0, curr = 0, sum = 0;
    for(int i = 1; i <= n; i++){
        while(j < m && curc + c[j + 1].second <= sumc - r[i].first + 1){
            j++;
            curc += c[j].second;
            cur += c[j].first * c[j].second;
        }
        sum += curr * (r[i - 1].first - r[i].first);
        sum += r[i].second;
        if((j == m ? 0ll : max(0ll, ((sumc - r[i].first + 1) - curc) * c[j + 1].first)) + cur < sum){
            cout << 0 << '\n';
            return;
        }
        if(j < m &&  c[j + 1].second * c[j + 1].first + cur < sum + (r[i].second + curr) * ((curc + c[j + 1].second) - (sumc - r[i].first + 1))){
            cout << 0 << '\n';
            return;
        }
        curr += r[i].second;
    }
    reverse(r + 1, r + n + 1);
    reverse(c + 1, c + m + 1);
    j = 0, cur = 0, curc = 0, curr = 0, sum = 0;
    for(int i = 1; i <= m; i++){
        while(j < n && curr + r[j + 1].second <= sumr - c[i].first + 1){
            j++;
            curr += r[j].second;
            cur += r[j].first * r[j].second;
        }
        sum += curc * (c[i - 1].first - c[i].first);
        sum += c[i].second;
        if((j == n ? 0ll : max(0ll, ((sumr - c[i].first + 1) - curr) * r[j + 1].first)) + cur < sum){
            cout << 0 << '\n';
            return;
        }
        if(j < n && r[j + 1].second * r[j + 1].first + cur < sum + (c[i].second + curc) * ((r[j + 1].second + curr) - (sumr - c[i].first + 1))){
            cout << 0 << '\n';
            return;
        }
        curc += c[i].second;
    }
    cout << 1;
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t; 
    while(t--){
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...