fork(3) download
copy 
  1. #include<bits/stdc++.h>
  2. #define loop(i,a,b) for(int i=a;i<b;i++)
  3. #define loopb(i,a,b) for(int i=a;i>=b;i--)
  4. #define loopm(i,a,b,step) for(int i=a;i<b;i+=step)
  5. #define loopbm(i,a,b,step) for(int i=a;i>=b;i-=step)
  6. #define pb(a) push_back(a)
  7. #define mp(a,b) make_pair(a,b)
  8. #define init(arr,val) memset(arr,val,sizeof(arr))
  9. #define INF 1000000007
  10. #define MOD 1000000007
  11. #define BINF 1000000000000000001
  12. #define int long long int
  13. #define double long double
  14.  
  15. using namespace std;
  16. int solve2(int x,int y,int z,int a,int b,int c)
  17. {
  18. 	int i,T,A[3],X[3],B[3],sum;
  19. 	int A1,B1,C1;
  20.  
  21.  
  22. 	int ans1=0,ans2=0,sum1,ans=0;
  23. 		//scanf("%d %d %d %d %d %d", &X[0], &X[1], &X[2], &A[0], &A[1], &A[2]);
  24. 		X[0]=x,X[1]=y,X[2]=z;
  25. 		A[0]=a,A[1]=b,A[2]=c;
  26. //		scanf("%d %d %d", &A[0], &A[1], &A[2]);
  27. //		X[0]=2, X[1]=4, X[2]=5;
  28. 		sort(X, X+3);
  29. 		B[0]=6*A[0],B[1]=3*A[1],B[2]=2*A[2];
  30. 		sum=(X[0]+X[1]+X[2]);
  31. 		sum1=sum;
  32. 		if(B[2]<B[0] && B[2]<B[1])
  33. 		{
  34. 			ans+=X[0]*A[2];
  35. 			sum-=3*X[0];
  36. 			A1=X[0],B1=X[1],C1=X[2];
  37. 			X[1]-=X[0],X[2]-=X[0];
  38. //			printf("3 : %d\n", ans);
  39. 			if(B[1]<B[0] && X[1]>0)
  40. 			{
  41. 				ans+=X[1]*A[1];
  42. 				sum-=2*X[1];
  43. 				X[2]-=X[1];
  44. //				printf("2 : %d\n", ans);
  45. 				if(X[2]>0)
  46. 				{
  47. 					ans+=sum*A[0];
  48. 					sum-=X[2];
  49. 					X[2]-=X[2];
  50. 				}
  51. 			}
  52. 			else{
  53. 				if(X[2]>0)
  54. 				{
  55. 					ans+=sum*A[0];
  56. 					sum-=sum;
  57. 					X[2]-=X[2];
  58. //					printf("1 : %d\n", ans);
  59. 				}
  60. 			}
  61. 			if(B[1]<B[0])
  62. 			{
  63. 				ans1=0;
  64. 				if(sum1%2==0){
  65. 					if(A1+B1>=C1)
  66. 					{
  67. 						ans1+=A[1]*(sum1/2);
  68. 					}
  69. 					else{
  70. 						ans1+=A[1]*(A1+B1) + (C1-A1-B1)*A[0];
  71. 					}
  72. 				}
  73. 				else{
  74. 					if(A1+B1>=C1)
  75. 					{
  76. 						ans2=A[1]*(sum1/2) + A[0];
  77. 						ans1+=A[1]*(sum1/2 -1) + A[2];
  78. 						ans1=(ans2<ans1) ? ans2 : ans1;
  79. 					}
  80. 					else{
  81. 						ans1+=A[1]*(A1+B1) + (C1-A1-B1)*A[0];
  82. 					}
  83. 				}
  84. //				printf("ans : %d | ans1 : %d\n", ans, ans1);
  85. 				ans=(ans<ans1) ? ans : ans1;
  86. 			}
  87. 		}
  88. 		else if(B[1]<B[0])
  89. 		{
  90. 			if(sum%2==0){
  91. 				if(X[0]+X[1]>=X[2])
  92. 				{
  93. 					ans+=A[1]*(sum/2);
  94. 				}
  95. 				else{
  96. 					//ans+=A[1]*(sum/2) + (sum-X[0]-X[1])*A[0];
  97. 					ans+=A[1]*(X[0]+X[1]) + (X[2]-X[0]-X[1])*A[0];
  98. 				}
  99. 			}
  100. 			else{
  101. 				if(X[0]+X[1]>=X[2])
  102. 				{
  103. 					ans+=A[1]*(sum/2) + A[0];
  104. 					ans1=A[1]*(sum/2 -1) + A[2];
  105. 					ans=(ans<ans1) ? ans : ans1;
  106. 				}
  107. 				else{
  108. 					//ans+=A[1]*(sum/2) + (sum-X[0]-X[1]+1)*A[0];
  109. 					ans+=A[1]*(X[0]+X[1]) + (X[2]-X[0]-X[1])*A[0];
  110. 				}
  111. 			}
  112. 		}
  113. 		else{
  114. 			ans+=sum*A[0];
  115. 		}
  116. 		return ans;
  117.  
  118. }
  119.  
  120. int solve1(int X,int Y,int Z,int A,int B,int C)
  121. {
  122. 	int f,g,h;
  123. 	int x,y,z,a,b,c;
  124. 	//cin>>f>>g>>h;
  125. 	f=X,g=Y,Z=h;
  126. 	//cin>>a>>b>>c;
  127. 	a=A,b=B,c=C;
  128. 	x=min(f,min(g,h));
  129. 	z=max(f,max(g,h));
  130. 	y=f+g+h-x-z;
  131.  
  132.  
  133. 	int ans=(x+y+z)*a;
  134. 	int ans1=BINF,ans2=BINF,ans3=BINF,ans4=BINF;
  135. 	if(z-(x+y)>=0)
  136. 	{
  137. 		 ans1=(x+y)*b+(z-x-y)*a;
  138.  
  139. 	}
  140. 	else
  141. 	  {
  142. 	  	 ans1=((x+y+z)/2)*b;
  143. 	  	 ans1+=((x+y+z)%2)*a;
  144. 	  }
  145.  
  146. 	 ans2=x*c+(z+y-x-x)*a;
  147.      ans3=x*c+(y-x)*b+(z-y)*a;
  148.      int r=z-y;
  149.  
  150. 	 loop(i,r,min(r+1,x+1))
  151. 	 {
  152. 	   int ans5=(x-i)*c;
  153. 	   int x2=i,y2=(y-x+i),z2=(z-x+i);
  154.  
  155. 	    if(z2-(x2+y2)>=0)
  156. 	{
  157. 		 ans5+=(x2+y2)*b+(z2-x2-y2)*a;
  158.  
  159. 	}
  160. 	else
  161. 	  {
  162. 	  	 ans5+=((x2+y2+z2)/2)*b;
  163. 	  	 ans5+=((x2+y2+z2)%2)*a;
  164. 	  }
  165.  
  166. 	  ans3=min(ans3,ans5);
  167.  
  168.  
  169. 	 }
  170.  
  171. 	loop(i,0,min((int)2,x+1))
  172. 	 {
  173. 	   int ans5=(i)*c;
  174. 	   int x2=x-i,y2=(y-i),z2=(z-i);
  175.  
  176. 	    if(z2-(x2+y2)>=0)
  177. 	{
  178. 		 ans5+=(x2+y2)*b+(z2-x2-y2)*a;
  179.  
  180. 	}
  181. 	else
  182. 	  {
  183. 	  	 ans5+=((x2+y2+z2)/2)*b;
  184. 	  	 ans5+=((x2+y2+z2)%2)*a;
  185. 	  }
  186.  
  187. 	  ans4=min(ans4,ans5);
  188.  
  189.  
  190. 	 }
  191.  
  192.  
  193.  
  194.  
  195. 	 ans=min(ans,min(ans1,min(ans2,min(ans3,ans4))));
  196. 	 return ans;
  197. }
  198.  
  199. #undef int
  200. int main()
  201. {
  202. #define int long long int
  203.     ios_base::sync_with_stdio(false);
  204.     cin.tie(NULL);
  205.     cout.tie(NULL);
  206.     srand(time(NULL));
  207.     loop(i,0,10)
  208.     {
  209.     	int x,y,z,a,b,c;
  210.     	x=rand()%10000;
  211.     	y=rand()%10000;
  212.     	z=rand()%10000;
  213.     	a=rand()%1000;
  214.     	b=rand()%1000;
  215.     	c=rand()%1000;
  216.     	int ans1=solve1(x,y,z,a,b,c);
  217.     	int ans2=solve2(x,y,z,a,b,c);
  218.     	if(ans1!=ans2)
  219.     	{
  220.     		cout<<x<<" "<<y<<" "<<z<<" "<<a<<" "<<b<<" "<<c<<endl;
  221.     		cout<<"expected: "<<ans1<<"  "<<"got: "<<ans2<<endl;
  222.     	}
  223.     }
  224.  
  225.     return 0;
  226. }
Success #stdin #stdout 0s 4352KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
7905 7405 8836 913 444 711
expected: 3744320  got: 5360412
3724 7140 6577 166 425 878
expected: 1803424  got: 2895206
646 8622 4425 954 23 422
expected: 7623962  got: 3504287
2180 9331 4503 592 720 32
expected: 5802992  got: 4600496
8941 6746 4439 295 426 436
expected: 3521321  got: 3565711
3683 3331 7193 871 596 989
expected: 2291868  got: 4336253
935 9320 5129 512 839 555
expected: 5077585  got: 6183483
3391 1837 5529 816 143 904
expected: 1530755  got: 993220
238 323 7236 742 916 308
expected: 281078  got: 5280610
8126 8209 5054 565 504 480
expected: 4142399  got: 4021103
https://ideone.com/IE4lQZ
language:
C++ (gcc 8.3)
created:
7 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!