fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long int
  5. const int mod = 1e9+7;
  6.  
  7. struct line
  8. {
  9.     int m, c;
  10. };
  11. vector< vector<line> > v;
  12. //Returns true if l2 isnt required anymore
  13. bool bad(line l1, line l2, line l3, int ismin)
  14. {
  15.     if(l3.m==l2.m) //Case when l2 and l3 are parallel
  16.     {
  17.         if(ismin)
  18.             return l2.c >= l3.c;
  19.         else
  20.             return l3.c >= l2.c;
  21.     }
  22.     if((l1.m - l2.m)*(l1.m - l3.m) > 0) //Checks if both have same signs to reverse the inequality
  23.         return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
  24.     else
  25.         return (l3.c - l1.c) * (l1.m - l2.m) >= (l2.c - l1.c) * (l1.m - l3.m);
  26. }
  27. void add(line l, int k, int ismin)
  28. {
  29.     while(v[k].size() > 1 && bad(v[k][v[k].size() - 2], v[k][v[k].size() - 1], l, ismin))
  30.         v[k].pop_back();
  31.     if(v[k].size() == 1 && v[k][0].m == l.m)
  32.     {
  33.         if(ismin)
  34.         {
  35.             if(v[k][0].c > l.c)
  36.             {
  37.                 v[k].pop_back();
  38.                 v[k].push_back(l);
  39.             }
  40.         }
  41.         else
  42.         {
  43.             if(v[k][0].c < l.c)
  44.             {
  45.                 v[k].pop_back();
  46.                 v[k].push_back(l);
  47.             }
  48.         }
  49.     }
  50.     else if(v[k].empty()||v[k][v[k].size()-1].m!=l.m)
  51.         v[k].push_back(l);
  52. }
  53. //Binary search to process query
  54. int query(int x, int k)
  55. {
  56.     if(v[k].empty())return -1000000000000000ll;
  57.     int l = 0, h = v[k].size();
  58.     while(h - l > 1)
  59.     {
  60.         int mid = (l + h) >> 1;
  61.         int intersect = floor(double(v[k][mid].c - v[k][mid - 1].c) / (v[k][mid - 1].m - v[k][mid].m));
  62.         if(x <= intersect)
  63.             h = mid; 
  64.         else
  65.             l = mid;
  66.     }
  67.     return v[k][l].m * x + v[k][l].c;
  68. }
  69.  
  70. #undef int
  71. int main()
  72. {   
  73. #define int long long int
  74.     ios_base::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.  
  78.     int t;
  79.     cin>>t;
  80.     while(t--)
  81.     {
  82.         int n, k;
  83.         cin>>n>>k;
  84.         vector<int> p(n), q(n);
  85.         for(int i = 0;i<n;i++)
  86.             cin>>p[i]>>q[i];
  87.         v.resize(k+1);
  88.         for(int i = 1;i<n;i++)
  89.             q[i] = max(q[i-1], q[i]);
  90.         for(int i = n-2;i>=0;i--)
  91.             p[i] = min(p[i], p[i+1]);
  92.         line cur;
  93.         cur.m = p[0];
  94.         cur.c = 0;
  95.         add(cur, 0, 0);
  96.         vector<int> ans(k+1);
  97.         //Finding the max
  98.         for(int i = 1;i<=n;i++)
  99.         {
  100.             for(int j = 1; j <= min(i, k); j++)
  101.                 ans[j] = query(q[i-1], j-1);
  102.             if(i==n)break;
  103.             for(int j = 1;j <= min(i, k); j++)
  104.             {
  105.                 if(ans[j]==-1000000000000000ll)continue;
  106.                 cur.m = p[i];
  107.                 cur.c = ans[j];
  108.                 add(cur, j, 0);
  109.             }
  110.         }
  111.         int ans1 = ans[k];
  112.         v.clear();
  113.         v.resize(k+1);
  114.         cur.m = q[n-1];
  115.         cur.c = 0;
  116.         add(cur, 0, 1);
  117.         //Finding the min
  118.         for(int i = n-1;i>=0;i--)
  119.         {
  120.             for(int j = 1;j<=min(n-i, k); j++)
  121.                 ans[j] = query(p[i], j-1);
  122.             if(i==0)break;
  123.             for(int j = 1;j<=min(n-i, k);j++)
  124.             {
  125.                 if(ans[j]==-1000000000000000ll)continue;
  126.                 cur.m = q[i-1];
  127.                 cur.c = ans[j];
  128.                 add(cur, j, 1);
  129.             }
  130.         }
  131.         cout<<ans[k]<<" "<<ans1<<endl;
  132.         v.clear();
  133.     }
  134.  
  135.     return 0;
  136. }
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
3
5 1
1 1
2 2
3 3
4 4
5 5
5 5
1 1
2 2
3 3
4 4
5 5
5 2
1 1
2 2
3 3
4 4
5 5
stdout
copy 
5 5
55 55
11 29
https://ideone.com/pWkx7f
language:
C++14 (gcc 8.3)
created:
6 years 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!