sacgajcvs

Untitled

Mar 29th, 2020
244
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.87 KB | None | 0 0
  1. /*
  2. _____ _ _ _ _
  3. |_ _| |__ ___ / \ _ __ ___| |__ _ _| |
  4. | | | '_ \ / _ \ / _ \ | '_ \/ __| '_ \| | | | |
  5. | | | | | | __// ___ \| | | \__ \ | | | |_| | |
  6. |_| |_| |_|\___/_/ \_\_| |_|___/_| |_|\__,_|_|
  7.  
  8. */
  9. #include<bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. #define ll long long
  13. #define pb push_back
  14. #define ppb pop_back
  15. #define endl '\n'
  16. #define mii map<ll,ll>
  17. #define msi map<string,ll>
  18. #define mis map<ll, string>
  19. #define rep(i,a,b) for(ll i=a;i<b;i++)
  20. #define repr(i,a,b) for(ll i=b-1;i>=a;i--)
  21. #define trav(a, x) for(auto& a : x)
  22. #define pii pair<ll,ll>
  23. #define vi vector<ll>
  24. #define vii vector<pair<ll, ll>>
  25. #define vs vector<string>
  26. #define all(a) (a).begin(),(a).end()
  27. #define F first
  28. #define S second
  29. #define sz(x) (ll)x.size()
  30. #define hell 1000000007
  31. #define lbnd lower_bound
  32. #define ubnd upper_bound
  33. #define max(a,b) (a>b?a:b)
  34. #define min(a,b) (a<b?a:b)
  35.  
  36. /* For Debugging */
  37. #define DEBUG cerr<<"\n>>>I'm Here<<<\n"<<endl;
  38. #define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
  39. #define what_is(x) cerr << #x << " is " << x << endl;
  40.  
  41. std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
  42. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  43. #define TIME cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
  44. #define DECIMAL(n) cout << fixed ; cout << setprecision(n);
  45. #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  46. using namespace __gnu_pbds;
  47. using namespace std;
  48. #define PI 3.141592653589793
  49. #define N 100005
  50. vi a,b;
  51. ll n;
  52. vector<vector<pii>>dp;
  53. vector<vector<bool>>vis;
  54.  
  55. pii fun(ll i,bool f)
  56. {
  57. if(i==n)
  58. {
  59. return {-1,hell};
  60. }
  61. if(vis[i][f])
  62. return dp[i][f];
  63. vis[i][f]=1;
  64. pii temp1=fun(i+1,f);
  65. pii temp2=fun(i+1,!f);
  66. if(f==0)
  67. {
  68. if(temp2.F==-1)
  69. temp2.F=0;
  70. temp2.F+=a[i];
  71. }
  72. else
  73. {
  74. if(temp2.S==hell)
  75. temp2.S=0;
  76. temp2.S+=b[i];
  77. }
  78. if(temp1.F*temp2.S>temp1.S*temp2.F)
  79. dp[i][f]=temp1;
  80. else
  81. dp[i][f]=temp2;
  82. return dp[i][f];
  83. }
  84.  
  85. void solve()
  86. {
  87. cin>>n;
  88. a.resize(n);
  89. b.resize(n);
  90. rep(i,0,n)
  91. cin>>a[i];
  92. rep(i,0,n)
  93. cin>>b[i];
  94. if(n==1)
  95. {
  96. cout<<-1<<endl;
  97. return;
  98. }
  99. dp = vector<vector<pii>>(n,vector<pii>(2,{-1,hell}));
  100. vis = vector<vector<bool>>(n,vector<bool>(2,false));
  101. pii temp1,temp2;
  102. temp1=fun(0,0);
  103. temp2=fun(0,1);
  104. if(temp1.F*temp2.S>temp1.S*temp2.F)
  105. cout<<temp1.F<<" "<<temp1.S<<endl;
  106. else
  107. cout<<temp2.F<<" "<<temp2.S<<endl;
  108. return;
  109. }
  110. int main()
  111. {
  112. #ifndef ONLINE_JUDGE
  113. // freopen ("input.txt","r",stdin);
  114. // freopen("output.txt","w",stdout);
  115. #endif
  116. FAST
  117. int TESTS=1;
  118. cin>>TESTS;
  119. while(TESTS--)
  120. {
  121. solve();
  122. }
  123. TIME
  124. return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment