fork download
copy 
  1. // BAI 4
  2.  
  3. #include "bits/stdc++.h"
  4. #define boostcode ios_base:: sync_with_stdio(0); cin.tie(0);
  5. #define openf freopen("input.inp", "r", stdin); freopen("output.out", "w", stdout);
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. ll n, W;
  12. int inp[4005][5];
  13. vector<vector<ll>> a[4005];
  14. vector<ll> cost[4005];
  15. ll f[4005];
  16. ll temp;
  17. ll res;
  18.  
  19. int main()
  20. {
  21.     boostcode;
  22.     //openf;
  23.  
  24.     cin >> n >> W;
  25.     for (int i = 1; i <= n; i++) {
  26.         cin >> inp[i][0] >> inp[i][1] >> inp[i][2] >> inp[i][3];
  27.     }
  28.     for (int i = 1; i <= n; i++) {
  29.         vector<ll> cur;
  30.         cur.push_back(inp[i][1]+inp[i][2]-inp[i][3]);
  31.         cur.push_back(inp[i][1]);
  32.         cur.push_back(inp[i][3]);
  33.         cur.push_back(1);
  34.         a[inp[i][0]].push_back(cur);
  35.     }
  36.     // CHECK HERE!:
  37.     for (int i = 1; i <= W; i++) {
  38.         //cout << "i: " << i << '\n';
  39.         priority_queue<vector<ll>, vector<vector<ll>>> pqueue;
  40.         for (auto x:a[i]) pqueue.push(x);
  41.         while (pqueue.size() && cost[i].size() <= W/i) {
  42.             vector<ll> cur = pqueue.top();
  43.             //cout << cur[0] << ' ' << cur[1] << ' ' << cur[2] << ' ' << cur[3] << '\n';
  44.             pqueue.pop();
  45.             cost[i].push_back(cur[0]);
  46.             vector<ll> out;
  47.             out.push_back(cur[1]+cur[2]*(cur[3]*cur[3]-(cur[3]+1)*(cur[3]+1)));
  48.             out.push_back(cur[1]);
  49.             out.push_back(cur[2]);
  50.             out.push_back(cur[3]+1);
  51.             pqueue.push(out);
  52.         }
  53.     }
  54.     for (int i = 1; i <= W; i++) {
  55.         for (ll x:cost[i]) {
  56.             for (int j = W; j >= i; j--) {
  57.                 f[j] = max(f[j], f[j-i] + x);
  58.             }
  59.         }
  60.     }
  61.  
  62.     res = (*max_element(f+1, f+W+1));
  63.     cout << res;
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FuQNia
language:
C++14 (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!