fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <iomanip>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <string>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <queue>
  12. #include <list>
  13. #include <map>
  14. #include <set>
  15.  
  16. #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
  17. #define FOR(i,a) For(i,1,a)
  18. #define Ford(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
  19. #define Rep(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
  20. #define REP(i,a) Rep(i,0,a)
  21. #define type(x) __typeof(x.begin())
  22. #define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )
  23. #define fi first
  24. #define se second
  25. #define dbg(x) cerr<<#x<<":"<<(x)<<endl
  26. #define dg(x) cerr<<#x<<":"<<(x)<<' '
  27. #define fill(x,y) memset(x,y,sizeof x)
  28. #define all(x) x.begin(),x.end()
  29. #define bin(x) (1LL<<(x))
  30. #define gcd __gcd
  31. #define pb push_back
  32. #define NEW(x,n) (x*)calloc(n,sizeof(x))
  33. #define mp make_pair
  34.  
  35. using namespace std;
  36.  
  37. typedef long long Lint;
  38. typedef pair<int,int> ii;
  39. typedef vector<int> vi;
  40. typedef vector<ii> vii;
  41.  
  42. const int inf = 1e9+5143;
  43. const Lint Linf = 1e18+5413;
  44.  
  45. template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
  46. template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
  47. template<class T> inline T abs(T a){return a>0 ? a : -a;}
  48. template<class T> inline T lcm(T a,T b){
  49.     return a/gcd(a,b)*b;
  50. }
  51.  
  52. inline int read(){
  53. 	int res = 0 ;int neg ;
  54. 	while(true){char ch = getchar();if(ch>='0' && ch<='9' || ch=='-'){if(ch=='-') neg = -1;else neg = 1 , res = ch-'0';break;} }
  55. 	while(true){char ch = getchar();if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';else break;}
  56. 	return res*neg;
  57. }
  58.  
  59. const int MAXN = 15010;
  60.  
  61. int N;
  62. int K;
  63.  
  64. int sum[MAXN];
  65.  
  66. vi vals;
  67. int pos[MAXN];
  68.  
  69. ii kd[MAXN*5];
  70. int n = MAXN;
  71.  
  72. inline void merge(ii &g,const ii &l,const ii &r){
  73.     g.fi = max(l.fi,r.fi);
  74.     g.se = min(l.se,r.se);
  75. }
  76.  
  77. void init(){
  78.     REP(i,MAXN*5) kd[i] = ii(-inf,inf);
  79. }
  80.  
  81. void modify(int x,ii val,int k=1,int b=1,int e=n){
  82.     if(b>x || e<x) return ;
  83.     if(b==e){
  84.         kd[k] = val;
  85.         return ;
  86.     }
  87.     modify(x,val,k*2,b,(b+e)/2);
  88.     modify(x,val,k*2+1,(b+e)/2+1,e);
  89.     merge(kd[k],kd[k+k],kd[k+k+1]);
  90. }
  91.  
  92. ii get(int x1,int x2,int k=1,int b=1,int e=n){
  93.     if(b>x2 || e<x1) return ii(-inf,inf);
  94.     if(b>=x1 && e<=x2) return kd[k];
  95.     ii res ; merge(res,get(x1,x2,k*2,b,(b+e)/2),get(x1,x2,k*2+1,(b+e)/2+1,e));
  96.     return res;
  97. }
  98.  
  99. ii get(int x){
  100.     int i = lower_bound(all(vals),x) - vals.begin()+1;
  101.     return get(i,n);
  102. }
  103.  
  104. bool can(int m){
  105.     init();
  106.     ii f ;
  107.     modify(pos[0],ii(0,0));
  108.     FOR(i,N){
  109.         f = get(sum[i]-m);
  110.         ++f.fi;
  111.         ++f.se;
  112.         modify(pos[i],f);
  113.     }
  114.     return f.se<=K && K<=f.fi;
  115. }
  116.  
  117. void doit(){
  118.  
  119.     N = read();
  120.     K = read();
  121.  
  122.     FOR(i,N) sum[i] = sum[i-1] + read();
  123.  
  124.     // here is compressing
  125.     vii vec;
  126.     vals.clear();
  127.     vec.pb(ii(0,0));
  128.     vals.pb(0);
  129.     FOR(i,N){
  130.         vals.pb(sum[i]);
  131.         vec.pb(ii(sum[i],i));
  132.     }
  133.     sort(all(vec));
  134.     sort(all(vals));
  135.     REP(i,vec.size()){
  136.         pos[vec[i].se] = i+1;
  137.     }
  138.  
  139.     // binary search
  140.     int l = -inf , r = inf ;
  141.     while(l+1<r){
  142.         int m = (l+r)>>1;
  143.         if(can(m)) r = m ;
  144.         else  l = m ;
  145.     }
  146.  
  147.     printf("%d\n",r);
  148.  
  149. }
  150.  
  151. int main(){
  152.  
  153.     int t=read();
  154.     while(t--){
  155.         doit();
  156.     }
  157.  
  158.     return 0;
  159. }
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
Time limit exceeded #stdin #stdout 5s 4052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bDCIjt
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!