fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, l, r) for (int i = l; i <= r; ++i)
  4. #define FORD(i, r, l) for (int i = r; i >= l; --i)
  5. #define ll long long
  6. #define pb push_back
  7. #define all(x) (x).begin(), (x).end()
  8. using namespace std;
  9.  
  10. const int N = 2e5;
  11. int n, m;
  12. ll a[N + 3], b[N + 3], s[N + 3], f[N + 3];
  13.  
  14. void maximize(ll &a, ll b) {
  15.     if (a < b) a = b;
  16. }
  17.  
  18. ll M(ll s,ll f,int pos) {
  19.     return (f - s) * max(a[pos], b[pos]);
  20. }
  21. ll cal(int pos,ll val) {
  22.     return (f[pos] - s[pos]) * val;
  23. }
  24.  
  25. namespace sub1 {
  26.     void solve() {
  27.         cout << M(s[1], f[1], 1);
  28.     }
  29. }
  30.  
  31. namespace sub2 {
  32.     void solve() {
  33.         int l = max(s[1] , s[2]);
  34.         int r = min(f[1] , f[2]);
  35.         if(l > r || m == 2) cout << M(s[1] , f[1] , 1) + M(s[2] , f[2] , 2);
  36.         else{
  37.             ll beforeLR = 0,inLR = 0,afterLR = 0;
  38.             if(s[1] < l) beforeLR = M(s[1] , l , 1);
  39.             else beforeLR = M(s[2] , l , 2);
  40.  
  41.             inLR = (r - l) * (b[1] + b[2] + max({0ll , a[1] -  b[1] , a[2] - b[2]}));
  42.             if(f[1] >= r) afterLR = M(r , f[1] , 1);
  43.             else afterLR = M(r , f[2] , 2);
  44.  
  45.             cout << beforeLR + inLR + afterLR;
  46.         }
  47.     }
  48. }
  49.  
  50. namespace sub3 {
  51.     ll dp[203][203], pre[203];
  52.     vector<int> pos;
  53.     void solve(){
  54.         memset(dp , -0x3f , sizeof(dp));
  55.         FOR(i, 1, n) pos.pb(s[i]), pos.pb(f[i]);
  56.         sort(all(pos));
  57.         m = min(m, n);
  58.         dp[0][0] = 0;
  59.  
  60.         FOR(j, 1, 2 * n - 1) {
  61.             vector<ll> dif;
  62.             int l = pos[j - 1];
  63.             int r = pos[j];
  64.             ll sum = 0;
  65.             FOR(i, 1, n)
  66.                 if(s[i] <= l && r <= f[i]){
  67.                     sum += b[i];
  68.                     dif.pb(a[i] - b[i]);
  69.                 }
  70.  
  71.             sort(all(dif), greater<ll>());
  72.             int k = min(m,(int) dif.size());
  73.  
  74.             FOR(o, 1, k) pre[o] = pre[o - 1] + max(0ll ,dif[o - 1]);
  75.             FOR(x, 0, m) FOR(y, 0, x) {
  76.                 maximize(dp[j][x], dp[j - 1][y] + (sum + pre[min(k, x)]) * (r - l) * 1ll);
  77.             }
  78.         }
  79.  
  80.         ll ans = -1e18;
  81.         FOR(j , 0 , m) ans = max(ans , dp[2 * n - 1][j]);
  82.         cout << ans;
  83.     }
  84. }
  85.  
  86. namespace sub4 {
  87.     struct Event {
  88.         int Time, id, Type;
  89.  
  90.         Event(int x = 0, int y = 0, int z = 0) {
  91.             Time = x;
  92.             id = y;
  93.             Type = z;
  94.         }
  95.  
  96.         bool operator < (const Event &ot) const {
  97.             if (Time != ot.Time) return Time < ot.Time;
  98.             return Type > ot.Type;
  99.         }
  100.     };
  101.  
  102.     vector <Event> Events;
  103.     multiset <ll> best, temp;
  104.     ll sum, res, ans;
  105.  
  106.     void add(ll profit) {
  107. 	// bỏ qua các số bé hoặc bằng 0 vì khi nhận nó kết quả sẽ không tối ưu
  108.         if (profit <= 0) return ;
  109.         if ((int) best.size() < m) {
  110.             sum += profit;
  111.             best.insert(profit);
  112.         }
  113.  
  114.         else if (profit > (*best.begin())) {
  115.             multiset <ll> :: iterator it = best.begin();
  116.             ll val = *it;
  117.             sum -= val;
  118.             best.erase(it);
  119.             temp.insert(val);
  120.  
  121.             best.insert(profit);
  122.             sum += profit;
  123.         }
  124.  
  125.         else temp.insert(profit);
  126.     }
  127.  
  128.     void del(ll profit) {
  129. 	// bỏ qua các số bé hoặc bằng 0 vì khi nhận nó kết quả sẽ không tối ưu
  130.         if (profit <= 0) return ;
  131.         if (best.find(profit) != best.end()) {
  132.             best.erase(best.find(profit));
  133.             sum -= profit;
  134.  
  135.             if (!temp.empty()) {
  136.                 multiset <ll> :: iterator it = prev(temp.end());
  137.                 ll val = *it;
  138.                 temp.erase(it);
  139.  
  140.                 best.insert(val);
  141.                 sum += val;
  142.             }
  143.         }
  144.  
  145.         else if (temp.find(profit) != temp.end())
  146.             temp.erase(temp.find(profit));
  147.     }
  148.  
  149.     void solve() {
  150.         FOR(i, 1, n) {
  151.             Events.push_back(Event(s[i], i, 1));
  152.             Events.push_back(Event(f[i], i, -1));
  153.         }
  154.         sort(Events.begin(), Events.end());
  155.  
  156.         int it = 0;
  157.         while (it < 2 * n) {
  158.             int T = Events[it].Time;
  159.  
  160.             while (it < 2 * n && Events[it].Time == T) {
  161.                 int id = Events[it].id;
  162.                 int Type = Events[it].Type;
  163.  
  164.                 if (Type == 1) {
  165.                     res += b[id];
  166.                     add(a[id] - b[id]);
  167.                 }
  168.  
  169.                 else {
  170.                     res -= b[id];
  171.                     del(a[id] - b[id]);
  172.                 }
  173.  
  174.                 ++it;
  175.             }
  176.  
  177.             if (it < 2 * n) {
  178.                 ll Length = Events[it].Time - T;
  179.                 ans += Length * (res + sum);
  180.             }
  181.         }
  182.  
  183.         cout << ans;
  184.     }
  185. }
  186.  
  187. signed main() {
  188.     ios_base::sync_with_stdio(0);
  189.     cin.tie(0); cout.tie(0);
  190.  
  191.     freopen("AICONF.inp" , "r" , stdin);
  192.     freopen("AICONF.out" , "w" , stdout);
  193.  
  194.     cin >> n >> m;
  195.     FOR(i, 1, n) cin >> a[i] >> b[i] >> s[i] >> f[i];
  196.  
  197.     if (n == 1) sub1::solve();
  198.     else if (n == 2) sub2::solve();
  199.     else if (n <= 100) sub3::solve();
  200.     else sub4::solve();
  201.  
  202.     return 0;
  203. }
  204.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R9Ufrf
language:
C++14 (clang 8.0)
created:
120 days ago
visibility:
secret

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!