fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=20000+10;
  27. const int INF=1000000;
  28. const int NUM=200+10;
  29.  
  30. int n,K;
  31. int b[MAX],c[MAX];
  32. int f[NUM][MAX],come_num[NUM][MAX];
  33. int q[MAX],bot,top;
  34.  
  35. int main()
  36. {
  37. 	int i,j,k;
  38. 	cin>>n;
  39. 	REP(i,1,n)
  40. 		scanf("%d",&b[i]);
  41. 	REP(i,1,n)
  42. 		scanf("%d",&c[i]);
  43. 	REP2(i,0,NUM)
  44. 		REP2(j,0,MAX)
  45. 			f[i][j]=INF;
  46. 	f[0][0]=0;
  47. 	REP(i,1,n)
  48. 	{
  49. 		int u=b[i];
  50. 		REP2(j,0,u)
  51. 		{
  52. 			bot=1;
  53. 			top=0;
  54. 			for(k=j;k<MAX;k+=u)
  55. 			{
  56. 				while(top>=bot && f[i-1][k] - k/u <f[i-1][ q[top] ] - q[top]/u )
  57. 					--top;
  58. 				q[++top]=k;
  59. 				while(q[bot]+c[i]*u<k && bot<=top)
  60. 					bot++;
  61. 				if(bot<=top)
  62. 				{
  63. 					int val=(k-q[bot])/u;
  64. 					f[i][k]=f[i-1][q[bot]]+val;
  65. 					come_num[i][k]=val;
  66. 				}
  67. 			}
  68. 		}
  69. 	}
  70. 	vector<int> ans(n+1,0);
  71. 	int sum=0;
  72. 	cin>>K;
  73. 	for(i=n;i>=1;--i)
  74. 	{
  75. 		int val=come_num[i][K];
  76. 		sum+=val;
  77. 		ans[i]=val;
  78. 		K-=b[i]*val;
  79. 	}
  80. 	cout<<sum<<endl;
  81. 	REP(i,1,n)
  82. 		cout<<ans[i]<<" ";
  83. 	cout<<endl;
  84. 	return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 36496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/tbOE67
language:
C++ (gcc 8.3)
created:
10 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!