fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 56789
  13. #define MAX 1037471823
  14. #define Q 10007
  15.  
  16. using namespace std;
  17.  
  18. int n, m, a, t, now, l, r, mid, w[MS], s[MS];
  19. int b, ans, dp[2][MS];
  20.  
  21. bool Check(int x)
  22. {
  23. 	int now = 0, t = 0;
  24. 	rep(i, 1, n) if (now + w[i] <= x) now += w[i]; else t++, now = w[i];
  25. 	if (t <= m) return true; else return false;
  26. }
  27.  
  28. int main()
  29. {
  30. 	scanf("%d%d", &n, &m);
  31. 	rep(i, 1, n) scanf("%d", &w[i]);
  32. 	rep(i, 1, n) s[i] = s[i-1] + w[i];
  33. 	rep(i, 1, n) if (a < w[i]) a = w[i];
  34. 	l = a, r = 56789012;
  35. 	while (l != r)
  36. 	{
  37. 		mid = (l+r) / 2;
  38. 		if (Check(mid)) r = mid; else l = mid+1;
  39. 	}
  40. 	t = l; printf("%d ", t); now = 0; dp[0][0] = 1;
  41. 	rep(i, 1, m+1)
  42. 	{
  43. 		now ^= 1;
  44. 		a = 0; b = dp[1-now][a] % Q; dp[now][0] = 0;
  45. 		rep(j, 1, n)
  46. 		{
  47. 			while (s[j] - s[a] > t) b = (b - dp[1-now][a++] + Q) % Q;
  48. 			dp[now][j] = b;
  49. 			b = (b + dp[1-now][j]) % Q;
  50. 		}
  51. 		ans = (dp[now][n] + ans) % Q;
  52. 	}
  53. 	printf("%d\n", ans);
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 4228KB
comments (?)
stdin
copy 
3 2
1 1 10
stdout
copy 
10 2
https://ideone.com/QBlLKZ
BZOJ 1044
language:
C++ (gcc 8.3)
created:
9 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!