fork download
copy 
  1.  
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. int x[1000000], y[1000000], delta2[1000000];
  7. long long sum[1000000], delta1[1000000];
  8.  
  9. int solve(int n, long long m, int z) {
  10. 	for (int i = 0; i < n; i ++) y[i] = x[i];
  11. 	for (int i = 0; i < n - 1; i ++)
  12. 		if (y[i+1] - y[i] > z) {
  13. 			m -= y[i+1] - y[i] - z;
  14. 			y[i+1] = y[i] + z;
  15. 		}
  16. 	for (int i = n - 1; i > 0; i --)
  17. 		if (y[i-1] - y[i] > z) {
  18. 			m -= y[i-1] - y[i] - z;
  19. 			y[i-1] = y[i] + z;
  20. 		}
  21. 	if (m < 0) return -1;
  22. 	for (int i = 0; i < n; i ++) sum[i] = 0;
  23. 	for (int i = 0; i < n; i ++) delta1[i] = 0;
  24. 	for (int i = 0; i < n; i ++) delta2[i] = 0;
  25. 	for (int i = 0; i < n; i ++) {
  26. 		int t = i + y[i] / z;
  27. 		if (t >= n) t = n - 1;
  28. 		delta1[t] += y[i] - (t - i) * z;
  29. 		delta2[t] ++;
  30. 		if (i > 0) delta1[i-1] -= y[i];
  31. 		delta2[i] --;
  32. 	}
  33. 	long long s = 0;
  34. 	int cnt = 0;
  35. 	for (int i = n - 1; i >= 0; i --) {
  36. 		s += delta1[i] + (long long)z * cnt;
  37. 		sum[i] += s;
  38. 		cnt += delta2[i];
  39. 	}
  40. 	for (int i = 0; i < n; i ++) delta1[i] = 0;
  41. 	for (int i = 0; i < n; i ++) delta2[i] = 0;
  42. 	for (int i = n - 1; i >= 0; i --) {
  43. 		int t = i - y[i] / z;
  44. 		if (t < 0) t = 0;
  45. 		delta1[t] += y[i] - (i - t) * z;
  46. 		delta2[t] ++;
  47. 		delta1[i] -= y[i];
  48. 		if (i > 0) delta2[i-1] --;
  49. 	}
  50. 	s = 0;
  51. 	cnt = 0;
  52. 	for (int i = 0; i < n; i ++) {
  53. 		s += delta1[i] + (long long)z * cnt;
  54. 		sum[i] += s;
  55. 		cnt += delta2[i];
  56. 	}
  57. 	for (int i = 0; i < n; i ++)
  58. 		if (sum[i] <= m) return i;
  59. 	return -1;
  60. }
  61.  
  62. int main() {
  63. 	int n;
  64. 	long long m;
  65. 	scanf("%d%lld", &n, &m);
  66. 	for (int i = 0; i < n; i ++) scanf("%d", &x[i]);
  67. 	long long sum = 0;
  68. 	for (int i = 0; i < n; i ++) sum += x[i];
  69. 	if (sum <= m) {
  70. 		printf("1 0\n");
  71. 		return 0;
  72. 	}
  73.  
  74. 	int head = 1, tail = 1000000000;
  75. 	while (head <= tail) {
  76. 		int mid = (head + tail) / 2;
  77. 		if (solve(n, m, mid) != -1)
  78. 			tail = mid - 1;
  79. 		else
  80. 			head = mid + 1;
  81. 	}
  82. 	printf("%d %d\n", solve(n, m, tail + 1) + 1, tail + 1);
  83.  
  84. 	return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 30072KB
comments (?)
stdin
copy 
16 15
8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5
stdout
copy 
1 2
https://ideone.com/nAocu
language:
C++ (gcc 8.3)
created:
14 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!