Advertisement
YEZAELP

CUBE-194: Déjà vu

Sep 12th, 2020
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const lli INF = 2e18;
  7.  
  8. int dp[100001];
  9. lli sum[100001];
  10.  
  11. int main(){
  12.  
  13.     int n;
  14.     scanf("%d", &n);
  15.  
  16.     lli ar[n+1];
  17.  
  18.     for(int i=1;i<=n;i++) scanf("%lld", &ar[i]);
  19.  
  20.     int sz = 0;
  21.     dp[0] = INF;
  22.     sum[0] = 0;
  23.  
  24.     for(int i=n;i>=1;i--){
  25.  
  26.         if(ar[i] <= dp[sz]){
  27.             sz ++;
  28.             dp[sz] = ar[i];
  29.             sum[sz] = sum[sz-1] + ar[i];
  30.         }
  31.  
  32.         else {
  33.             int l = 1, r = sz, mn = INF;
  34.             while(l <= r){
  35.                 int mid = (l + r) / 2;
  36.                 if(ar[i] > dp[mid]){
  37.                     r = mid - 1;
  38.                     mn = min(mn, mid);
  39.                 }
  40.                 else {
  41.                     l = mid + 1;
  42.                 }
  43.             }
  44.             dp[mn] = ar[i];
  45.             sum[mn] = sum[mn-1] + ar[i];
  46.         }
  47.  
  48.     }
  49.  
  50.     printf("%d %lld", sz, sum[sz]);
  51.  
  52.     return 0;
  53. }
Advertisement
RAW Paste Data Copied
Advertisement