fork download
copy 
  1. /* Author : Nguyen Thanh Tung */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl 		         '\n'
  6. #define int 		         long long
  7.  
  8. using namespace 	         std;
  9.  
  10. typedef pair<int, int>       ii;
  11.  
  12. const int       N            = 3e3 + 7;
  13. const long long oo           = 1e18 + 7;
  14. const long long MOD          = 1e9 + 7;
  15.  
  16. int n, s, w[N], v[N], b[N], a[N];
  17. int d = 0;
  18. int dp[N][N];
  19.  
  20. void input() {
  21.     cin >> n >> s;
  22.     for(int i = 1; i <= n; ++i) {
  23.         cin >> w[i] >> v[i] >> b[i] >> a[i];
  24.         d += (b[i] + a[i]);
  25.     }
  26. }
  27.  
  28. void sub2() {
  29.     for(int i = 1; i <= n; ++i) {
  30.         for(int j = 1; j <= s; ++j) {
  31.             dp[i][j] = dp[i - 1][j];
  32.             if(w[i] <= j) {
  33.                 dp[i][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
  34.             }
  35.         }
  36.     }
  37.     cout << dp[n][s];
  38. }
  39.  
  40. void sub3() {
  41.     vector<int> f(s + 1, 0);
  42.     for(int i = 1; i <= n; ++i) {
  43.         for(int j = s; j >= w[i]; --j) {
  44.             int maxk = (j / w[i]);
  45.             for(int k = 1; k <= maxk; ++k) {
  46.                 int tmp = f[j - k * w[i]] + k * v[i] - a[i] * k * k + b[i] * (k > 0);
  47.                 f[j] = max(f[j], tmp);
  48.             }
  49.         }
  50.     }
  51.     cout << f[s];
  52. }
  53.  
  54. #define TASK "code"
  55.  
  56. signed main () {
  57.     ios_base::sync_with_stdio (false);
  58.     cin.tie(nullptr), cout.tie(nullptr);
  59.     input();
  60.     if(d == 0) {
  61.         return sub2(), 0;
  62.     }
  63.     if(n <= 3000 && s <= 3000) {
  64.         return sub3(), 0;
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OU6fFj
language:
C++14 (clang 8.0)
created:
4 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!