Advertisement
Guest User

Untitled

a guest
Jan 21st, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define all(x) x.begin(), x.end()
  4. #define rall(x) x.rbegin(), x.rend()
  5. #define F first
  6. #define S second
  7. #define pb push_back
  8. #define ll long long
  9. #define ld long double
  10. #define int long long
  11.  
  12. #pragma GCC optimize("Ofast")
  13. #pragma GCC target("sse3,sse4")
  14.  
  15. //#define TASK ""
  16.  
  17. using namespace std;
  18.  
  19. const int MAXN = 200001;
  20. const int INF = 1e9;
  21.  
  22. ll power(ll x, ll n, ll mod = 1e18 + 7) {
  23. if (n == 0) return 1ll;
  24. if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
  25. ll tmp = power(x, n >> 1ll, mod);
  26. return (tmp * tmp) % mod;
  27. }
  28.  
  29. int gcd (int a, int b) {
  30. if (b == 0) return a;
  31. return gcd (b, a % b);
  32. }
  33.  
  34. vector<int> getPref(vector<int> &a) {
  35. vector<int> ans(a.size());
  36. int sum = 0;
  37. for (int i = a.size() - 1; i >= 0; i--) {
  38. if (a[i] == 1) sum++;
  39. ans[i] = sum;
  40. }
  41. return ans;
  42. }
  43.  
  44. vector<int> max_cnt(vector<int> &a, vector<int> &pref) {
  45. int sum = 0;
  46. vector<int> ans(count(all(a), 0) + 1);
  47. if (ans.size() != 0)
  48. ans[0] = count(all(a), 1);
  49. for (int i = 0; i < a.size(); i++) {
  50. if (a[i] == 0) sum++;
  51. ans[sum] = max(ans[sum], pref[i]);
  52. }
  53. return ans;
  54. }
  55.  
  56.  
  57. signed main() {
  58. #ifndef LOCAL
  59. #ifdef TASK
  60. freopen(TASK".in", "r", stdin);
  61. freopen(TASK".out", "w", stdout);
  62. #endif
  63. #endif
  64. #ifdef LOCAL
  65. //freopen("/Users/alekseygolub/Desktop/ะก++/ABS/ABS/input.txt", "r", stdin);
  66. #endif
  67. iostream::sync_with_stdio(0);
  68. cin.tie(0);
  69. cout.tie(0);
  70. srand(924653523);
  71. // == SOLUTION == //
  72. int n;
  73. cin >> n;
  74. vector<int> a, b;
  75. for (int i = 0; i < n; i++) {
  76. int x;
  77. cin >> x;
  78. a.pb(x);
  79. }
  80. int m;
  81. cin >> m;
  82. for (int i = 0; i < m; i++) {
  83. int x;
  84. cin >> x;
  85. b.pb(x);
  86. }
  87.  
  88. if (n * m == 0) {
  89. cout << 0 << '\n';
  90. return 0;
  91. }
  92.  
  93. vector<int> a_pref = getPref(a);
  94. vector<int> b_pref = getPref(b);
  95. vector<int> x = max_cnt(a, a_pref);
  96. vector<int> y = max_cnt(b, b_pref);
  97. int SZ = min(x.size(), y.size());
  98. int ans = 0;
  99. for (int i = 0; i < SZ; i++) {
  100. ans = max(ans, i + min(x[i], y[i]));
  101. }
  102. cout << ans << '\n';
  103.  
  104.  
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement