Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define bigdata ios::sync_with_stdio(false);cin.tie(nullptr);
- using namespace std;
- typedef long long ll;
- const ll INF = 1E9 + 7;
- ll n, m;
- vector<ll> a;
- vector<ll> b;
- vector<ll> prefa;
- vector<ll> prefb;
- ll ask(vector<ll> &pref, ll l, ll r, bool zero){
- ll tmp;
- if (l == 0){
- tmp = pref[r];
- }
- else{
- tmp = pref[r] - pref[l - 1];
- }
- if (zero){
- return tmp;
- }
- else{
- return r - l + 1 - tmp;
- }
- }
- int main(){
- bigdata;
- cin >> n;
- a.resize(n);
- prefa.resize(n);
- for (ll i = 0; i < n; ++i){
- cin >> a[i];
- }
- if (a[0] == 0){
- prefa[0] = 1;
- }
- for (ll i = 1; i < n; ++i){
- if (a[i] == 0){
- prefa[i] = prefa[i - 1] + 1;
- }
- else{
- prefa[i] = prefa[i - 1];
- }
- }
- cin >> m;
- b.resize(m);
- prefb.resize(m);
- for (ll i = 0; i < m; ++i){
- cin >> b[i];
- }
- if (b[0] == 0){
- prefb[0] = 1;
- }
- for (ll i = 1; i < m; ++i){
- if (b[i] == 0){
- prefb[i] = prefb[i - 1] + 1;
- }
- else{
- prefb[i] = prefb[i - 1];
- }
- }
- ll best = 0;
- if (m < n){
- best = max(min(ask(prefa, 0, n - 1, true), ask(prefb, 0, m - 1, true)), min(ask(prefa, 0, n - 1, false), ask(prefb, 0, m - 1, false)));
- for (ll i = 0; i < m; ++i){
- cout << 0 << " " << i << " " << m - 1 << endl;
- ll zerob = ask(prefb, 0, i, true);
- ll oneb = ask(prefb, i, m - 1, false);
- if (zerob + oneb > best){
- auto k = lower_bound(prefa.begin(), prefa.end(), zerob);
- if (k == prefa.end()){
- break;
- }
- int pos = k - prefa.begin();
- ll onea = ask(prefa, pos, n - 1, false);
- if (onea >= oneb){
- best = zerob + oneb;
- }
- }
- }
- }
- else{
- best = max(min(ask(prefa, 0, n - 1, true), ask(prefb, 0, m - 1, true)), min(ask(prefa, 0, n - 1, false), ask(prefb, 0, m - 1, false)));
- for (ll i = 0; i < n; ++i){
- ll zeroa = ask(prefa, 0, i, true);
- ll onea = ask(prefa, i, n - 1, false);
- if (zeroa + onea > best){
- auto k = lower_bound(prefb.begin(), prefb.end(), zeroa);
- if (k == prefb.end()){
- break;
- }
- int pos = k - prefb.begin();
- ll oneb = ask(prefb, pos, m - 1, false);
- if (oneb >= onea){
- best = zeroa + onea;
- }
- }
- }
- }
- cout << best;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement