fork download
copy 
  1. /*
  2. وَلَا تُخْزِنِي يَوْمَ يُبْعَثُونَ•يَوْمَ لَا يَنفَعُ مَالٌ وَلَا بَنُونَ•إِلَّا مَنْ أَتَى اللَّهَ بِقَلْبٍ سَلِيم❤
  3. */
  4. #include <bits/stdc++.h>
  5. #define ll long long
  6. #define el endl
  7. using namespace std;
  8. void saf_sofa()
  9. {
  10.     if (fopen("in.txt", "r"))
  11.     {
  12.         freopen("in.txt", "r", stdin);
  13.         freopen("out.txt", "w", stdout);
  14.     }
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(NULL);
  17. }
  18. int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
  19. int dy[] = { -1, 1, 0, 0, -1, 1, 1, -1 };
  20. const int N = 105, mod = 1e9 + 7;
  21. int dp[N][100001], w[100001], val[N];
  22. int n, W;
  23. int DP(int i, int x)
  24. {
  25. 	if (x > W)
  26. 		return -1e9;
  27. 	if (i == n)
  28. 		return 0;
  29. 	if (~dp[i][x])
  30. 		return dp[i][x];
  31. 	int ch1 = DP(i + 1, x);
  32. 	int ch2 = DP(i + 1, x + w[i]) + val[i];
  33. 	return dp[i][x] = max(ch1, ch2);
  34. }
  35. void solve()
  36. {
  37. }
  38. int main()
  39. {
  40. 	saf_sofa();
  41. 	int t_ = 1;
  42. 	// cin >> t_;
  43. 	while (t_--)
  44. 	{
  45.  
  46. 		cin >> n >> W;
  47. 		for (int i = 0; i < n; i++)
  48. 		{
  49. 			cin >> w[i] >> val[i];
  50. 		}
  51.  
  52. 		memset(dp, -1, sizeof dp);
  53. 		// solve();
  54. 		cout << DP(0, 0);
  55. 	}
  56. }
  57. /*
  58.  
  59. وَليتَ الذي بَيني وبينَك عامِرٌ وبَيني وبَينَ العَـٰالمينَ خرَابُ
  60.  
  61. */
Success #stdin #stdout 0.01s 44628KB
comments (?)
stdin
copy 
3 8
3 30
4 50
5 60
stdout
copy 
90
https://ideone.com/KliY6W
language:
C++ (gcc 8.3)
created:
1 day 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!