fork(1) download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2025-10-21 10:00:32
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2025-10-21 15:55:28
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name ""
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)5e5+10;
  54. int n,W;
  55.  
  56. struct Data {
  57. 	int v,w;
  58. 	bool operator<(const Data &other) {
  59. 		return w > other.w;
  60. 	}
  61. } a[N];
  62.  
  63. namespace sub3 {
  64.  
  65. 	bool approved() {
  66. 		return n <= 1e3 and W <= 1e4;
  67. 	}
  68.  
  69. 	void solve(void)
  70. 	{
  71. 		sort(a+1,a+n+1);
  72. 		mii dp;
  73. 		dp[W] = 0;
  74. 		FOR(i,1,n)
  75. 			for (auto &x : dp)
  76. 				if (x.fi >= a[i].w)
  77. 					maximize(dp[x.fi-a[i].w],x.se+a[i].v);
  78. 		int ans = 0;
  79. 		for (auto &x : dp) maximize(ans,x.se);
  80. 		cout << ans;
  81. 	}
  82.  
  83. }
  84.  
  85. namespace sub5 {
  86.  
  87. 	bool approved() {
  88. 		int x = a[1].w;
  89. 		FOR(i,1,n)
  90. 			if (a[i].w != x) return false;
  91. 		return W <= 1e8;
  92. 	}
  93.  
  94. 	void solve(void)
  95. 	{
  96. 		sort(a+1,a+n+1,[&](Data &x, Data &y) {
  97. 			return x.v > y.v;
  98. 		});
  99. 		int w0 = a[1].w, k = min(W/w0,n);
  100. 		int ans = 0;
  101. 		FOR(i,1,k) ans += a[i].v;
  102. 		cout << ans;
  103. 	}
  104.  
  105. }
  106.  
  107. namespace sub6 {
  108.  
  109. 	map<int,vi> val;
  110. 	int pre1[N],pre2[N];
  111.  
  112. 	bool approved() {
  113. 		set<int> s;
  114. 		FOR(i,1,n) s.insert(a[i].w);
  115. 		return W <= 1e8 and sz(s) <= 2;
  116. 	}
  117.  
  118. 	void solve(void)
  119. 	{
  120. 		FOR(i,1,n) val[a[i].w].pb(a[i].v);
  121. 		int val1 = 0, len1 = 0, val2 = 0, len2 = 0;
  122. 		for (auto x : val)
  123. 			if (!val1)
  124. 			{
  125. 				len1 = sz(x.se);
  126. 				val1 = x.fi;
  127. 				sort(all(x.se),greater<int>());
  128. 				FOR(i,0,len1-1)
  129. 					pre1[i+1] = pre1[i]+x.se[i];
  130. 			}
  131. 			else
  132. 			{	
  133. 				len2 = sz(x.se);
  134. 				val2 = x.fi;
  135. 				sort(all(x.se),greater<int>());
  136. 				FOR(i,0,len2-1)
  137. 					pre2[i+1] = pre2[i]+x.se[i];
  138. 			}
  139. 		int ans = 0;
  140. 		FOR(i,0,len1-1)
  141. 			if (val1*i >= W) break;
  142. 			else 
  143. 			{
  144. 				int cur = (W-(i*val1))/val2;
  145. 				maximize(ans,pre1[i]+pre2[cur]);
  146. 			}
  147. 		cout << ans;
  148. 	}
  149.  
  150. }
  151.  
  152. namespace sub7 {
  153.  
  154. 	vi val[N];
  155.  
  156. 	vi mergeSort(vi &a, vi &b)
  157. 	{
  158. 		int n = sz(a)-1, m = sz(b)-1;
  159. 		vi ans(n+m+1);
  160. 		int pos = 0;
  161. 		FOR(i,0,n+m)
  162. 		{
  163. 			int l = max(0LL,i-m), r = min(i,n);
  164. 			if (pos < l) pos = l;
  165. 			if (pos > r) pos = r;
  166. 			while (pos < r and a[pos+1]+b[i-(pos+1)] >= a[pos]+b[i-pos]) 
  167. 				++pos;
  168. 			ans[i] = a[pos]+b[i-pos];
  169. 		}
  170. 		return ans;
  171. 	}
  172.  
  173. 	vi calc(vi &v, int tmp, int sz)
  174. 	{
  175. 		vi ans;
  176. 		int pos = 1, sum = v[0];
  177. 		while (pos < sz(v) and tmp > 0)
  178. 		{
  179. 			tmp--;
  180. 			sum = v[pos++];
  181. 		}
  182. 		ans.pb(sum);
  183. 		while (pos < sz(v))
  184. 		{
  185. 			int cur = pos+sz;
  186. 			while (pos < sz(v) and pos < cur)
  187. 				sum = v[pos++];
  188. 			ans.pb(sum);
  189. 		}
  190. 		return ans;
  191. 	}
  192.  
  193. 	void solve(void)
  194. 	{
  195. 		sort(a+1,a+n+1,[&](Data &x, Data &y) {
  196. 			if (x.w == y.w) return x.v > y.v;
  197. 			return x.w < y.w;
  198. 		});	
  199. 		while (n and a[n].w > W) n--;
  200. 		vi vec;
  201. 		FOR(i,1,n) vec.pb(a[i].w);
  202. 		vec.erase(unique(all(vec)),vec.end());
  203. 		int len = sz(vec);
  204. 		if (vec.empty())
  205. 		{
  206. 			cout << 0 << endl;
  207. 			return;
  208. 		}
  209. 		FOR(i,0,len-1) val[i].pb(0);
  210. 		int pos = 0;
  211. 		FOR(i,1,n)
  212. 		{
  213. 			if (vec[pos] != a[i].w) pos++;
  214. 			val[pos].pb(a[i].v);
  215. 		}
  216. 		FOR(i,0,pos)
  217. 			FOR(j,1,sz(val[i])-1) val[i][j] += val[i][j-1];
  218. 		FOR(i,0,pos-1)
  219. 		{
  220. 			int cur = (W-(W/vec[i+1])*vec[i+1])/vec[i], sz = vec[i+1]/vec[i];
  221. 			val[i] = calc(val[i],cur,sz);
  222. 			val[i+1] = mergeSort(val[i],val[i+1]);
  223. 		}
  224. 		int tmp = W/vec[pos];
  225. 		cout << val[pos][min(tmp,(int)sz(val[pos])-1)];
  226. 	}
  227.  
  228. }
  229.  
  230. bool M2;
  231. signed main()
  232. {
  233.     fast;
  234.     if (fopen(name".inp","r"))
  235.     {
  236.     	freopen(name".inp","r",stdin);
  237.     	freopen(name".out","w",stdout);
  238.     }
  239.     cin >> n >> W;
  240.     FOR(i,1,n) cin >> a[i].v >> a[i].w;
  241.     if (sub3::approved()) return sub3::solve(), time(), memory(), 0;
  242.     if (sub5::approved()) return sub5::solve(), time(), memory(), 0;
  243.     if (sub6::approved()) return sub6::solve(), time(), memory(), 0;
  244.     sub7::solve();
  245.     time();
  246.     memory();
  247.     return 0;
  248. }
  249. // ██░ ██  █    ██  ███▄    █   ▄████
  250. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  251. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  252. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  253. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  254. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  255. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  256. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  257. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 19348KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:8.463ms.
26.7036 MB
https://ideone.com/W20aQN
language:
C++14 (gcc 8.3)
created:
6 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!