fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int n,k;
  6. long long a[1005],b[1005];
  7. long long dp[1005][1005];
  8.  
  9. void f_min(int x,int l,int r,int ll,int rr){
  10.     if (l>r || ll>rr) return;
  11.     int mid=(l+r)>>1;
  12.     int pos=ll;
  13.     long long cur;
  14.     for (int i=ll;i<=min(rr,mid);++i) {
  15.         cur=dp[x-1][i-1]+a[i]*b[mid];
  16.         if (cur<dp[x][mid]) {
  17.             pos=i;
  18.             dp[x][mid]=cur;
  19.         }
  20.     }
  21.     f_min(x,l,mid-1,ll,pos);
  22.     f_min(x,mid+1,r,pos,rr);
  23. }
  24.  
  25. inline long long solve_min() {
  26.     for (int i=0;i<=n;++i)
  27.         for (int j=0;j<=k;++j)
  28.             dp[j][i]=1e18;
  29.     dp[0][0]=0;
  30.     for (int i=1;i<=k;++i)
  31.         f_min(i,1,n,1,n);
  32.     return dp[k][n];
  33. }
  34.  
  35. void f_max(int x,int l,int r,int ll,int rr){
  36.     if (l>r || ll>rr) return;
  37.     int mid=(l+r)>>1;
  38.     int pos=ll;
  39.     long long cur;
  40.     for (int i=ll;i<=min(rr,mid);++i) {
  41.         cur=dp[x-1][i-1]+a[i]*b[mid];
  42.         if (cur>dp[x][mid]) {
  43.             pos=i;
  44.             dp[x][mid]=cur;
  45.         }
  46.     }
  47.     f_max(x,l,mid-1,ll,pos);
  48.     f_max(x,mid+1,r,pos,rr);
  49. }
  50.  
  51.  
  52. inline long long solve_max() {
  53.     for (int i=0;i<=n;++i)
  54.         for (int j=0;j<=k;++j)
  55.             dp[j][i]=-1e18;
  56.     dp[0][0]=0;
  57.     for (int i=1;i<=k;++i)
  58.         f_max(i,1,n,1,n);
  59.     return dp[k][n];
  60. }
  61. int main(){
  62.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  63.     int tt;
  64.     cin>>tt;
  65.     while (tt--) {
  66.         cin>>n>>k;
  67.         for (int i=1;i<=n;++i) {
  68.             cin>>a[i]>>b[i];
  69.         }
  70.         long long last=1e9;
  71.         for (int i=n;i>0;--i) {
  72.             last=min(last,a[i]);
  73.             a[i]=last;
  74.         }
  75.         last=-1e9;
  76.         for (int i=1;i<=n;++i) {
  77.             last=max(last,b[i]);
  78.             b[i]=last;
  79.         }
  80.         cout<<solve_min()<<" "<<solve_max()<<'\n';
  81.     }
  82. }
  83.  
Success #stdin #stdout 0s 4332KB
comments (?)
stdin
copy 
1
4 2
-1 -3
-1 -3
3 -3
0 10
// correct answer for min is -7
stdout
copy 
3 3
https://ideone.com/WQSZWr
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!