fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <algorithm>
  5. #include <fstream>
  6. #include <string>
  7. #include <string.h>
  8.  
  9. using namespace std;
  10.  
  11. int N,L,i,Mid,f1,f2,CurrentSizeLimit,Ans,iter,R;
  12. long long Budget;
  13. int X[100005];
  14. long long presums[100005];
  15.  
  16. long long BudgetQueryLeft(int where,int howmany) {
  17. 	return 1LL*howmany*X[where]-(presums[where]-presums[where-howmany]);
  18. }
  19.  
  20. long long BudgetQueryRight(int where,int howmany) {
  21. 	return (presums[where+howmany-1]-presums[where-1])-1LL*howmany*X[where-1];
  22. }
  23.  
  24. int FindRightCount(int where,long long budget) {
  25. 	int Ret=0,L=1,R=N-where+1,Mid,iter;
  26. 	for (iter=0;iter<17;iter++) {
  27. 		Mid=(L+R)>>1;
  28. 		if (BudgetQueryRight(where,Mid)<=budget) {
  29. 			Ret=max(Ret,Mid);
  30. 			L=Mid+1;
  31. 		} else R=Mid;
  32. 	}
  33. 	return Ret;
  34. }	
  35.  
  36.  
  37. int main() {
  38. 	//freopen("input.txt","r",stdin);
  39.  
  40. 	scanf("%d%d%lld", &N,&L,&Budget);
  41. 	for (i=1;i<=N;i++) {
  42. 		scanf("%d", &X[i]);
  43. 		presums[i]=presums[i-1]+X[i];
  44. 	}
  45.  
  46. 	CurrentSizeLimit=0;
  47.  
  48. 	for (i=1;i<=N;i++) {
  49. 		CurrentSizeLimit++;
  50. 		while (BudgetQueryLeft(i,CurrentSizeLimit)>Budget) CurrentSizeLimit--;
  51. 		L=1; R=CurrentSizeLimit;
  52. 		for (iter=0;iter<17;iter++) {
  53. 			Mid=(L+R)>>1;
  54. 			f1=FindRightCount(i+1,Budget-BudgetQueryLeft(i,Mid));
  55. 			Ans=max(Ans,Mid+f1);
  56. 			if (Mid<R) {
  57. 				f2=FindRightCount(i+1,Budget-BudgetQueryLeft(i,Mid+1));
  58. 				Ans=max(Ans,Mid+1+f2);
  59. 				if (Mid+f1<Mid+1+f2)
  60. 					L=Mid;
  61. 				else
  62. 					R=Mid;
  63. 			}
  64. 		}
  65. 	}
  66.  
  67. 	printf("%d\n",Ans);
  68.  
  69. 	return 0;
  70. }
Success #stdin #stdout 0s 4272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/cKYo9H
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!