| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1322822 | syanvu | Bodyguards (CEOI10_bodyguards) | C++20 | 0 ms | 0 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 = 1e6 + 1, MX = 40, inf = 1e18, p = 11, p1 = 17, mod = 1e9 + 7, mod1 = 998244353;
int cr[N], cc[N];
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;
for(int j = sumr + 1; j <= sumr + r[i].second; j++) cr[j] = r[i].first;
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;
for(int j = sumc + 1; j <= sumc + c[i].second; j++) cc[j] = c[i].first;
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);
sort(rc + 1, rc + sumr + 1);
sort(cc + 1, cc + sumc + 1);
int pr1[sumc + 1] = {}, pr2[sumr + 1] = {};
for(int i = 1; i <= n; i++){
if(r[i].first > sumc){
cout << 0 << '\n';
return;
}
pr1[sumc - r[i].first + 1] += r[i].second;
}
for(int i = 1; i <= m; i++){
if(c[i].first > sumr){
cout << 0 << '\n';
return;
}
pr2[sumr - c[i].first + 1] += c[i].second;
}
int cur = 0;
for(int i = 1; i <= sumr; i++){
pr2[i] += pr2[i - 1];
cur -= pr2[i];
cur += cr[i];
if(cur < 0){
cout << 0 << '\n';
return;
}
}
cur = 0;
for(int i = 1; i <= sumc; i++){
pr1[i] += pr1[i - 1];
cur -= pr1[i];
cur += cc[i];
if(cur < 0){
cout << 0 << '\n';
return;
}
}
cout << 1 << '\n';
}
signed main(){
SS
// freopen("trains.in", "r", stdin);
// freopen("trains.out", "w", stdout);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}