YEZAELP

CUBE-197: Fair and Square

Oct 17th, 2021
724
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int K = 50 + 10;
  5. const int N = 1500 + 10;
  6. const int INF = 1e9;
  7. using pi = pair <int, int>;
  8. int tree[3][N];
  9. int sz, sum;
  10. int ar[N], med[N][N], dp[K][N];
  11. vector <int> coor;
  12.  
  13. int Index(int x){
  14.     int l = 1, r = sz - 1;
  15.     while(l <= r){
  16.         int mid = (l + r) / 2;
  17.         if(coor[mid] == x) return mid;
  18.         else if(coor[mid] < x) l = mid + 1;
  19.         else r = mid - 1;
  20.     }
  21. }
  22.  
  23. void Update(int pst, int val1, int val2){
  24.     for(int i = pst; i < sz; i += i & -i){
  25.         tree[1][i] += val1;
  26.         tree[2][i] += val2;
  27.     }
  28. }
  29.  
  30. pi Query(int pst, pi q = {0, 0}){
  31.     for(int i = pst; i > 0; i -= i & -i){
  32.         q.first += tree[1][i];
  33.         q.second += tree[2][i];
  34.     }
  35.     return q;
  36. }
  37.  
  38. void Median(int i, int j, int len){
  39.     int mp = (len / 2) + (len % 2), ms = INF, mv = 0, mc = INF, mn = INF;
  40.     int l = 1, r = sz - 1;
  41.     while(l <= r){
  42.         int mid = (l + r) / 2;
  43.         pi q = Query(mid);
  44.         int bsc = q.first, bss = q.second;
  45.         if(bsc >= mp){
  46.             r = mid - 1;
  47.             ms = min(ms, bss);
  48.             mc = min(mc, bsc);
  49.             mn = min(mn, mid);
  50.         }
  51.         else l = mid + 1;
  52.     }
  53.     mv = coor[mn];
  54.     med[i][j] = ( mc * mv - ms ) + ( (sum - ms) - (len - mc) * mv );
  55. }
  56.  
  57. int main(){
  58.  
  59.     int n, part;
  60.     scanf("%d%d", &n, &part);
  61.  
  62.     for(int i=1;i<=n;i++){
  63.         scanf("%d", &ar[i]);
  64.         coor.push_back(ar[i]);
  65.     }
  66.  
  67.     sort(coor.begin(), coor.end());
  68.     coor.resize( unique(coor.begin(), coor.end()) - coor.begin() );
  69.     coor.insert(coor.begin(), 0);
  70.     sz = coor.size(); // for(int i=1;i<sz;i++) printf("%d ", coor[i]);
  71.  
  72.     for(int l=1;l<=n;l++){
  73.         int i, j; /// [i,j] l = j-i+1
  74.         for(j=l;j<=n;j++){ i = j - l + 1;
  75.             if(i > 1) Update(Index(ar[i-1]), -1, -ar[i-1]), sum -= ar[i-1];
  76.             Update(Index(ar[j]), 1, ar[j]), sum += ar[j];
  77.             Median(i, j, l);
  78.         }
  79.         l ++;
  80.         for(i=n-l+1;i>=1;i--){ j = i + l - 1;
  81.             if(j < n) Update(Index(ar[j+1]), -1, -ar[j+1]), sum -= ar[j+1];
  82.             Update(Index(ar[i]), 1, ar[i]), sum += ar[i];
  83.             Median(i, j, l);
  84.         }
  85.     }
  86.  
  87.     dp[0][0] = 0;
  88.     for(int i=1;i<=n;i++) dp[0][i] = INF;
  89.  
  90.     for(int k=1;k<=part;k++){
  91.         for(int j=1;j<=n;j++){
  92.             dp[k][j] = INF;
  93.             for(int i=1;i<=j;i++){
  94.                 dp[k][j] = min(dp[k][j], dp[k-1][i-1] + med[i][j]);
  95.             }
  96.         }
  97.     }
  98.  
  99.     printf("%d", dp[part][n]);
  100.  
  101.     return 0;
  102. }
  103.  
RAW Paste Data