fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 1e5+5;
  11.  
  12. struct ez{int fi, se, thi;};
  13. int n, m, a[maxN], b[maxN], s[maxN], l[maxN], dp[55][1005][1005];
  14. ez trace[55][1005][1005];
  15.  
  16. void sub2()
  17. {
  18. 	for(int ac=1; ac<=m; ac+=1)
  19. 	{
  20. 		int k;
  21. 		cin>>a[ac]>>b[ac]>>k;
  22. 		memset(dp, 0, sizeof(dp));
  23. 		map<int,bool>mp;
  24. 		for(int j=1; j<=k; j+=1) cin>>l[j], mp[l[j]] = 1;
  25. 		for(int i=1; i<=n; i+=1) dp[i][0][0] = 0;
  26. 		if(!mp[1])
  27. 		{
  28. 			dp[1][s[1]][0] = 1;
  29. 			dp[1][0][s[1]] = 1;
  30. 		}
  31. 		for(int i=2; i<=n; i+=1)
  32. 		{
  33. 			if(mp[l[i]]) continue;
  34. 			for(int w1=0; w1<=a[ac]; w1+=1)
  35. 			{
  36. 				for(int w2=0; w2<=b[ac]; w2+=1)
  37. 				{
  38. 					if(w1 + w2 == 0) continue;
  39. 					if(dp[i][w1][w2] <= dp[i-1][w1][w2])
  40. 					{
  41. 						dp[i][w1][w2] = dp[i-1][w1][w2];
  42. 						trace[i][w1][w2] = {i-1,w1,w2};
  43. 					}
  44. 					if(w1+s[i] <= 1000)
  45. 					{
  46. 						if(dp[i][w1+s[i]][w2] <= dp[i-1][w1][w2]+1)
  47. 						{
  48. 							dp[i][w1+s[i]][w2] = dp[i-1][w1][w2]+1;
  49. 							trace[i][w1+s[i]][w2] = {i-1,w1,w2};
  50. 						}
  51. 					}
  52. 					if(w2+s[i] <= 1000)
  53. 					{
  54. 						if(dp[i][w1][w2+s[i]] <= dp[i-1][w1][w2]+1)
  55. 						{
  56. 							dp[i][w1][w2+s[i]] = dp[i-1][w1][w2]+1;
  57. 							trace[i][w1][w2+s[i]] = {i-1,w1,w2};
  58. 						}					
  59. 					}
  60.  
  61. 				}
  62. 			}
  63. 		}
  64. 		int ans = 0;
  65. 		for(int w1=0; w1<=a[ac]; w1+=1)
  66. 		{
  67. 			for(int w2=0; w2<=b[ac]; w2+=1)
  68. 			{
  69. 				ans = max(ans, dp[n][w1][w2]);
  70. 			}
  71. 		}
  72. 		if(ac == 1)
  73. 		{
  74. 			bool stop = 0;
  75. 			vector<int>res(n+1, 0);
  76. 			for(int w1=0; w1<=a[ac]; w1+=1)
  77. 			{
  78. 				for(int w2=0; w2<=b[ac]; w2+=1)
  79. 				{
  80. 					if(dp[n][w1][w2] == ans)
  81. 					{
  82. 						int x = n, y = w1, z = w2;
  83. 						while(x != 1)
  84. 						{
  85. 							int last_x = x, last_y = y, last_z = z;
  86. 							ez tmp = trace[x][y][z];
  87. 							x = tmp.fi;
  88. 							y = tmp.se;
  89. 							z = tmp.thi;
  90. 							if(last_y != y) res[last_x] = 1;
  91. 							if(last_z != z) res[last_x] = 2;
  92. 							// cout<<last_x<<" "<<last_y<<" "<<last_z<<'\n';
  93. 							// cout<<x<<" "<<y<<" "<<z<<'\n';
  94. 						}
  95. 						if(y) res[1] = 1;
  96. 						if(z) res[1] = 2;
  97. 						stop = 1;
  98. 					}
  99. 					if(stop) break;
  100. 				}
  101. 				if(stop) break;
  102. 			}
  103. 			cout<<ans<<'\n';
  104. 			for(int i=1; i<=n; i+=1) cout<<res[i]; cout<<'\n';
  105. 		}
  106. 		else cout<<ans<<' ';
  107. 	}
  108. }
  109.  
  110. void sub3()
  111. {
  112. 	sort(s+1, s+n+1);
  113. }
  114.  
  115. // dp[i][j][k] la so anh toi da co the sao chep khi di den dinh i, j va k la so dung luong da dung trong 2 o cung
  116. int32_t main()
  117. {
  118. 	ios_base::sync_with_stdio(0); cin.tie(0);
  119. 	cin>>n>>m;
  120. 	for(int i=1; i<=n; i+=1) cin>>s[i];
  121. 	sub2();
  122. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lj92bA
language:
C++14 (gcc 8.3)
created:
3 days 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!