fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int maxn = 1111;
  4. long long P[maxn], Q[maxn];
  5. long long dp[maxn][maxn];
  6. using ll = long long;
  7. const ll is_query = -(1LL<<62);
  8. struct Line {
  9.     ll m, b;
  10.     mutable function<const Line*()> succ;
  11.     bool operator<(const Line& rhs) const {
  12.         if (rhs.b != is_query) return m < rhs.m;
  13.         const Line* s = succ();
  14.         if (!s) return 0;
  15.         ll x = rhs.m;
  16.         return b - s->b < (s->m - m) * x;
  17.     }
  18. };
  19. struct HullDynamic : public multiset<Line> { // will maintain upper hull for maximum
  20.     bool bad(iterator y) {
  21.         auto z = next(y);
  22.         if (y == begin()) {
  23.             if (z == end()) return 0;
  24.             return y->m == z->m && y->b <= z->b;
  25.         }
  26.         auto x = prev(y);
  27.         if (z == end()) return y->m == x->m && y->b <= x->b;
  28.         return (x->b - y->b)*(z->m - y->m) >= (y->b - z->b)*(y->m - x->m);
  29.     }
  30.     void insert_line(ll m, ll b) {
  31.         auto y = insert({ m, b });
  32.         y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
  33.         if (bad(y)) { erase(y); return; }
  34.         while (next(y) != end() && bad(next(y))) erase(next(y));
  35.         while (y != begin() && bad(prev(y))) erase(prev(y));
  36.     }
  37.     ll eval(ll x) {
  38.         auto l = *lower_bound((Line) { x, is_query });
  39.         return l.m * x + l.b;
  40.     }
  41. };
  42. int main(){
  43.     int cs;
  44.     scanf("%d", &cs);
  45.     while(cs--){
  46.         int n, k;
  47.         scanf("%d %d", &n, &k);
  48.         for(int e = 1; e <= n; e++) scanf("%lld %lld", P + e, Q + e);
  49.         for(int e = n-1; e >= 1; e--) P[e] = min(P[e], P[e+1]);
  50.         for(int e = 2; e <= n; e++) Q[e] = max(Q[e], Q[e-1]);
  51.         long long mi, ma;
  52.         const long long inf = 1ll<<56;
  53.         {
  54.             for(int e = 0; e <= k; e++){
  55.                 for(int f = 0; f <= n; f++){
  56.                     dp[e][f] = -inf;
  57.                 }
  58.             }
  59.             dp[0][0] = 0;
  60.             for(int e = 1; e <= k; e++){
  61.                 HullDynamic q;
  62.                 if(dp[e-1][0] != -inf)
  63.                     q.insert_line(P[1], dp[e-1][0]);
  64.                 for(int f = 1; f <= n; f++){
  65.                     if(!q.empty()) dp[e][f] = max(dp[e][f], q.eval(Q[f]));
  66.                     if(dp[e-1][f] != -inf)
  67.                         q.insert_line(P[f+1], dp[e-1][f]);
  68.                 }
  69.             }
  70.             mi = dp[k][n];
  71.         }
  72.         {
  73.             for(int e = 0; e <= k; e++){
  74.                 for(int f = 0; f <= n; f++){
  75.                     dp[e][f] = inf;
  76.                 }
  77.             }
  78.             dp[0][0] = 0;
  79.             for(int e = 1; e <= k; e++){
  80.                 HullDynamic q;
  81.                 if(dp[e-1][0] != inf)
  82.                     q.insert_line(-P[1], -dp[e-1][0]);
  83.                 for(int f = 1; f <= n; f++){
  84.                     if(!q.empty()) dp[e][f] = min(dp[e][f], -q.eval(Q[f]));
  85.                     if(dp[e-1][f] != inf)
  86.                         q.insert_line(-P[f+1], -dp[e-1][f]);
  87.                 }
  88.             }
  89.             ma = dp[k][n];
  90.         }
  91.         cout << ma << " " << mi << endl;
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 4384KB
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/61Va4F
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!