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 F[MAXN];
  70.  
  71. inline void update(ii &a,const ii &b){
  72.     umax(a.fi,b.fi);
  73.     umin(a.se,b.se);
  74. }
  75.  
  76. void init(){
  77.     REP(i,MAXN) F[i] =ii(-inf,inf);
  78. }
  79.  
  80. void put(int x,ii val){
  81.     x = (N+1) -x + 1 ;
  82.     while(x<MAXN){
  83.         update(F[x],val);
  84.         x+=x&-x;
  85.     }
  86. }
  87.  
  88. ii get(int x){
  89.     int i = lower_bound(all(vals),x)-vals.begin()+1;
  90.     i = (N+1) - i + 1 ;
  91.     ii res = ii(-inf,inf);
  92.     while(i>0){
  93.         update(res,F[i]);
  94.         i-=i&-i;
  95.     }
  96.     return res;
  97. }
  98.  
  99. bool can(int m){
  100.     init();
  101.     ii f ;
  102.     put(pos[0],ii(0,0));
  103.     FOR(i,N){
  104.         f = get(sum[i]-m);
  105.         ++f.fi;
  106.         ++f.se;
  107.         put(pos[i],f);
  108.     }
  109.     return f.se<=K && K<=f.fi;
  110. }
  111.  
  112. void doit(){
  113.  
  114.     N = read();
  115.     K = read();
  116.  
  117.     FOR(i,N) sum[i] = sum[i-1] + read();
  118.  
  119.     vii vec;
  120.     vals.clear();
  121.     vec.pb(ii(0,0));
  122.     vals.pb(0);
  123.     FOR(i,N){
  124.         vals.pb(sum[i]);
  125.         vec.pb(ii(sum[i],i));
  126.     }
  127.     sort(all(vec));
  128.     sort(all(vals));
  129.     REP(i,vec.size()){
  130.         pos[vec[i].se] = i+1;
  131.     }
  132.  
  133.  
  134.     int l = -inf , r = inf ;
  135.     while(l+1<r){
  136.         int m = (l+r)>>1;
  137.         if(can(m)) r = m ;
  138.         else  l = m ;
  139.     }
  140.  
  141.     printf("%d\n",r);
  142.  
  143. }
  144.  
  145. int main(){
  146.  
  147.     int t=read();
  148.     while(t--){
  149.         doit();
  150.     }
  151.  
  152.     return 0;
  153. }
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
Time limit exceeded #stdin #stdout 5s 3536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zwB2iP
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!