ccbeginner

TIOJ 1208

Feb 23rd, 2020
99
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TIOJ 1208
  2. /******************************************************************************
  3.  
  4.                               Online C++ Compiler.
  5.                Code, Compile, Run and Debug C++ program online.
  6. Write your code in this editor and press "Run" button to compile and execute it.
  7.  
  8. *******************************************************************************/
  9.  
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12.  
  13. int arr[20001], sum[20001];
  14. int n,k;
  15.  
  16. int msort(const int lhs, const int rhs, const int val){
  17.     if(lhs == rhs-1)return (val <= sum[lhs])? 1 : 0;
  18.     int mid = (lhs + rhs) / 2;
  19.     int ret = msort(lhs, mid, val) + msort(mid, rhs, val);
  20.     vector<int> left, right;
  21.     for(int i = lhs; i < mid; ++i)left.emplace_back(sum[i]);
  22.     for(int i = mid;  i < rhs; ++i)right.emplace_back(sum[i]);
  23.     for(int i = 0, j = 0; i < left.size(); ++i){
  24.         while(j < right.size() && val > right[j] - left[i])++j;
  25.         ret += right.size() - j;
  26.     }
  27.     for(int i = 0, j = 0; i < left.size(); ++i){
  28.         while(j < right.size() && left[i] > right[j]){
  29.             sum[lhs+i+j] = right[j];
  30.             ++j;
  31.         }
  32.         sum[lhs+i+j] = left[i];
  33.     }
  34.     return ret;
  35. }
  36.  
  37. int cnt(int val){
  38.     for(int i = 1; i <= n; ++i)sum[i] = sum[i-1] + arr[i];
  39.     return msort(1, n+1, val);
  40. }
  41.  
  42. int main(){
  43.     while(cin >> n >> k){
  44.         if(n == 0 && k == 0)break;
  45.         for(int i = 1; i <= n; ++i)cin >> arr[i];
  46.         int big = 2e9, small = -2e9;
  47.         while(big >= small){
  48.             int mid = (big+small) / 2;
  49.             if(cnt(mid) < k)big = mid - 1;
  50.             else small = mid + 1;
  51.         }
  52.         cout << big << '\n';
  53.     }
  54.     return 0;
  55. }
RAW Paste Data