fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. #define oo 999999
  6. #define f(a,b) ((a)>(b)?(b):(a))
  7. #define g(a,b) ((a)>(b)?(a):(b))
  8. int n, H[2105][2105], h[77], t[77], ts[77];
  9. pair <int, int> b[77];
  10. int main () {
  11. 	scanf("%d",&n);
  12. 	for (int i = 0; i < n; i++) scanf("%d%d",&b[i].first,&b[i].second);
  13. 	sort(b, b+n); reverse(b, b+n);
  14. 	for (int i = 0; i < n; i++) h[i] = b[i].first, t[i] = b[i].second, ts[i+1] = ts[i]+t[i];
  15. 	for (int i = 0; i <= ts[n]; i++) for (int j = 0; j <= ts[n]; j++) H[i][j] = oo;
  16. 	H[0][0] = 0;
  17. 	for (int i = 0; i < n; i++) {
  18. 		for (int ta = ts[i+1]; ta >= 0; ta--) {
  19. 			for (int tb = ts[i+1]; tb >= 0; tb--) {
  20. 				if (ta > t[i]) H[ta][tb] = f(H[ta][tb], H[ta-t[i]][tb]);
  21. 				if (ta == t[i]) H[ta][tb] = f(H[ta][tb], H[ta-t[i]][tb] + h[i]);
  22. 				if (tb > t[i]) H[ta][tb] = f(H[ta][tb], H[ta][tb-t[i]]);
  23. 				if (tb == t[i]) H[ta][tb] = f(H[ta][tb], H[ta][tb-t[i]] + h[i]);
  24. 			}
  25. 		}
  26. 	}
  27. 	int res = 2147483647;
  28. 	for (int ta = 1; ta <= ts[n]; ta++) for (int tb = 1; tb <= ts[n]; tb++)
  29. 		res = f(res, g(g(ta,tb),(ts[n]-ta-tb))*(h[0]+H[ta][tb]));
  30. 	printf("%d",res);
  31. }
  32.  
Success #stdin #stdout 0s 20616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2147483647
https://ideone.com/tRAYLz
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!