SHARE
TWEET

Untitled

a guest Oct 28th, 2019 143 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <stdlib.h>     /* srand, rand */
  5. #include <time.h>       /* time */
  6. #define mt make_tuple
  7. #define ll long long
  8. #define eb emplace_back
  9. #define fi first
  10. #define pb push_back
  11. #define all(x) (x).begin(), (x).end()
  12. #define rall(x) (x).rbegin(), (x).rend()
  13. #define forn(i, n) for (int i = 0; i < (int)(n); ++i)
  14. #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
  15. #define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];}
  16. #define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";}
  17. #define mod(a,b) ((a%b +b)%b)
  18. #define bit(x,i) (x&(1<<i))  //select the bit of position i of x
  19. #define lowbit(x) ((x)&((x)^((x)-1))) //get the lowest bit of x
  20. #define hBit(msb,n) asm("bsrl %1,%0" : "=r"(msb) : "r"(n)) //get the highest bit of x, maybe the fastest
  21. #define max(a,b) (a<b?b:a)
  22. #define min(a,b) (a>b?b:a)
  23. #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
  24. #define IN(i,l,r) (l<i&&i<r)
  25. #define LINR(i,l,r) (l<=i&&i<=r)
  26. #define LIN(i,l,r) (l<=i&&i<r)
  27. #define INR(i,l,r) (l<i&&i<=r)
  28. #define lastEle(vec) vec[vec.size()-1]
  29. #define SZ(x) ((int)((x).size()))
  30. #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
  31. #define ll long long
  32. #define ull unsigned long long
  33. #define ui unsigned int
  34. #define us unsigned short
  35. #define INF 1001001001
  36. #define PI 3.1415926535897932384626
  37.  
  38. using namespace std;
  39.  using namespace __gnu_pbds;
  40.  template <typename T>
  41.  using ordered_set =
  42.     tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  43.  
  44. typedef pair<int, int> pii;
  45. typedef vector<int> vi;
  46. typedef vector<pii> vpi;
  47. typedef vector<vi> vvi;
  48.  
  49. void err(istream_iterator<string> it) {}
  50. template<typename T, typename... Args>
  51. void err(istream_iterator<string> it, T a, Args... args) {
  52.     cerr << *it << " = " << a << endl;
  53.     err(++it, args...);
  54. }
  55.  
  56. //----------------------------------------------------------------------------------------------------------------------
  57.  
  58.  
  59. void swap(char &a, char & b){
  60.     char temp = a;
  61.     a = b;
  62.     b = temp;
  63. }
  64.  
  65. const ll MOD = 998244353;
  66. const int MAXN = 1e5 + 5;
  67.  
  68. //char grid[MAXN][MAXN];
  69.  
  70. void add_self(ll &a, ll b){
  71.     a+= b;
  72.     while(a > MOD){
  73.         a-=MOD;
  74.     }
  75. }
  76.  
  77.  
  78. ll inf = 1LL*1e18;
  79.  
  80. void no(){
  81.     cout <<"NO" << endl;
  82.     exit(0);
  83. }
  84.  
  85. void yes(){
  86.     cout <<"YES" << endl;
  87.     exit(0);
  88. }
  89.  
  90.  
  91.  
  92.  
  93.  
  94. bool check( ll c, vector< ll > & arr,ll k){
  95.     ll ans = arr[1]/c;
  96.     ll rem = arr[1]%c;
  97.     for(int i = 2;i < arr.size();i++){
  98.         ll cnt = (arr[i] + rem)/c;
  99.         ans += cnt;
  100.         if(arr[i] + rem < c){
  101.             rem = arr[i];
  102.         }else{
  103.             rem = (arr[i] + rem)%c;
  104.         }
  105.     }
  106.     return ans >= k;
  107. }
  108.  
  109.  
  110. int main(){
  111.    
  112.     int t;
  113.     cin >> t;
  114.     while(t--){
  115.         int n;
  116.         cin >> n;
  117.         ll k; cin >> k;
  118.         vector< ll > arr (n + 1);
  119.         ll sum = 0;
  120.         for(int i = 1;i <= n;i++){
  121.             cin >> arr[i];
  122.             sum += arr[i];
  123.         }
  124.         ll left = 1; ll right = sum + 10;
  125.         ll ans = 0;
  126.         while(left <= right){
  127.             ll c = left + (right - left)/2;
  128.             if(check(c,arr,k)){
  129.                 ans = max(c,ans);
  130.                 left = c + 1;
  131.             }else{
  132.                 right = c - 1;
  133.             }
  134.         }
  135.  
  136.         cout << ans*k << endl;
  137.     }
  138.  
  139.     return 0;
  140. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top