Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define bigdata ios::sync_with_stdio(false);cin.tie(nullptr);
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const ll INF = 1E9 + 7;
  7. ll n, m;
  8. vector<ll> a;
  9. vector<ll> b;
  10. vector<ll> prefa;
  11. vector<ll> prefb;
  12. ll ask(vector<ll> &pref, ll l, ll r, bool zero){
  13.     ll tmp;
  14.     if (l == 0){
  15.         tmp = pref[r];
  16.     }
  17.     else{
  18.         tmp = pref[r] - pref[l - 1];
  19.     }
  20.     if (zero){
  21.         return tmp;
  22.     }
  23.     else{
  24.         return r - l + 1 - tmp;
  25.     }
  26. }
  27. int main(){
  28.     bigdata;
  29.     cin >> n;
  30.     a.resize(n);
  31.     prefa.resize(n);
  32.     for (ll i = 0; i < n; ++i){
  33.         cin >> a[i];
  34.     }
  35.     if (a[0] == 0){
  36.         prefa[0] = 1;
  37.     }
  38.     for (ll i = 1; i < n; ++i){
  39.         if (a[i] == 0){
  40.             prefa[i] = prefa[i - 1] + 1;
  41.         }
  42.         else{
  43.             prefa[i] = prefa[i - 1];
  44.         }
  45.     }
  46.     cin >> m;
  47.     b.resize(m);
  48.     prefb.resize(m);
  49.     for (ll i = 0; i < m; ++i){
  50.         cin >> b[i];
  51.     }
  52.     if (b[0] == 0){
  53.         prefb[0] = 1;
  54.     }
  55.     for (ll i = 1; i < m; ++i){
  56.         if (b[i] == 0){
  57.             prefb[i] = prefb[i - 1] + 1;
  58.         }
  59.         else{
  60.             prefb[i] = prefb[i - 1];
  61.         }
  62.     }
  63.     ll best = 0;
  64.     if (m < n){
  65.         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)));
  66.         for (ll i = 0; i < m; ++i){
  67.             cout << 0 << " " << i << " " << m - 1 << endl;
  68.             ll zerob = ask(prefb, 0, i, true);
  69.             ll oneb = ask(prefb, i, m - 1, false);
  70.             if (zerob + oneb > best){
  71.                 auto k = lower_bound(prefa.begin(), prefa.end(), zerob);
  72.                 if (k == prefa.end()){
  73.                     break;
  74.                 }
  75.                 int pos = k - prefa.begin();
  76.                 ll onea = ask(prefa, pos, n - 1, false);
  77.                 if (onea >= oneb){
  78.                     best = zerob + oneb;
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     else{
  84.         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)));
  85.         for (ll i = 0; i < n; ++i){
  86.             ll zeroa = ask(prefa, 0, i, true);
  87.             ll onea = ask(prefa, i, n - 1, false);
  88.             if (zeroa + onea > best){
  89.                 auto k = lower_bound(prefb.begin(), prefb.end(), zeroa);
  90.                 if (k == prefb.end()){
  91.                     break;
  92.                 }
  93.                 int pos = k - prefb.begin();
  94.                 ll oneb = ask(prefb, pos, m - 1, false);
  95.                 if (oneb >= onea){
  96.                     best = zeroa + onea;
  97.                 }
  98.             }
  99.         }
  100.     }
  101.     cout << best;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement