fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int, int>
  13. #define pll pair<ll, ll>
  14. #define pli pair<ll, int>
  15. #define vi vector<int>
  16. #define vll vector<ll>
  17.  
  18. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef unsigned int ui;
  24.  
  25. using namespace std;
  26.  
  27. const int M = 1e9 + 7;
  28. const int INF = 1e9 + 7;
  29. const ll INFLL = (ll)2e18 + 7LL;
  30. const ld PI = acos(-1);
  31.  
  32. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  33. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  34.  
  35. template<class _, class __>
  36.     bool minimize(_ &x, const __ y){
  37.         if(x > y){
  38.             x = y;
  39.             return true;
  40.         } else return false;
  41.     }
  42. template<class _, class __>
  43.     bool maximize(_ &x, const __ y){
  44.         if(x < y){
  45.             x = y;
  46.             return true;
  47.         } else return false;
  48.     }
  49.  
  50. //--------------------------------------------------------------
  51.  
  52. const int MaxN = 3007;
  53.  
  54. int n,W;
  55. struct adj{
  56.     int w,v,a,b;
  57. } a[MaxN];
  58.  
  59. namespace sub1 {
  60.     bool check() {
  61.         return n <= 100 && W <= 100;
  62.     }
  63.  
  64.     ll f[107];
  65.  
  66.     void sol() {
  67.         memset(f,0,sizeof(f));
  68.         for (int i=1;i<=n;i++) {
  69.             for (int j=W;j>=a[i].w;j--) {
  70.                 for (int k=1;k<=j/a[i].w;k++) {
  71.                     maximize(f[j],f[j-k*a[i].w] + 1LL*k*a[i].v - a[i].a*k*k + a[i].b);
  72.                 }
  73.             }
  74.         }
  75.         cout << f[W];
  76.     }
  77. }
  78.  
  79. namespace sub2{
  80.     bool check() {
  81.         for (int i=1;i<=n;i++) if (a[i].a != 0 || a[i].b != 0) return false;
  82.         return n <= 3000 && W <= 3000;
  83.     }
  84.  
  85.     ll f[3007];
  86.  
  87.     void sol() {
  88.         memset(f,0,sizeof(f));
  89.         for (int i=1;i<=n;i++) {
  90.             for (int j=a[i].w;j<=W;j++) {
  91.                 maximize(f[j],f[j-a[i].w] + a[i].v);
  92.             }
  93.         }
  94.         cout << f[W];
  95.     }
  96. }
  97.  
  98. void sol() {
  99.     cin >> n >> W;
  100.     for (int i=1;i<=n;i++) cin >> a[i].w >> a[i].v >> a[i].b >> a[i].a;
  101.     if (sub1::check()) {
  102.         sub1::sol();
  103.         return;
  104.     }
  105.     if (sub2::check()) {
  106.         sub2::sol();
  107.         return;
  108.     }
  109. }
  110.  
  111. int main() {
  112. 	freopen("test.inp","r",stdin);
  113. 	freopen("test.out","w",stdout);
  114. 	FAST
  115. 	int t=1;
  116. //	cin >> t;
  117. 	while (t--) sol();
  118. }
  119.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/puOScX
language:
C++ (gcc 8.3)
created:
7 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!