fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 500000;
  5. const int MAXM = 20;
  6. const ll INF = 1e18;
  7.  
  8. int n, k, m;
  9. vector<int> a;
  10. vector<int> R;
  11. vector<int> L;
  12. vector<vector<ll>> dp;
  13.  
  14. void computeR() {
  15.     R.resize(n + 1);
  16.     unordered_map<int, int> freq;
  17.     deque<int> min_deq, max_deq;
  18.     int r = 1;
  19.     for (int l = 1; l <= n; l++) {
  20.         if (r < l) r = l;
  21.         while (r <= n) {
  22.             if (freq[a[r]] > 0) {
  23.                 break;
  24.             }
  25.             freq[a[r]]++;
  26.             while (!min_deq.empty() && a[min_deq.back()] >= a[r]) {
  27.                 min_deq.pop_back();
  28.             }
  29.             min_deq.push_back(r);
  30.             while (!max_deq.empty() && a[max_deq.back()] <= a[r]) {
  31.                 max_deq.pop_back();
  32.             }
  33.             max_deq.push_back(r);
  34.             int current_min = a[min_deq.front()];
  35.             int current_max = a[max_deq.front()];
  36.             if (current_max - current_min > k) {
  37.                 freq[a[r]]--;
  38.                 min_deq.pop_back();
  39.                 max_deq.pop_back();
  40.                 break;
  41.             }
  42.             r++;
  43.         }
  44.         R[l] = r - 1;
  45.         freq[a[l]]--;
  46.         if (!min_deq.empty() && min_deq.front() == l) {
  47.             min_deq.pop_front();
  48.         }
  49.         if (!max_deq.empty() && max_deq.front() == l) {
  50.             max_deq.pop_front();
  51.         }
  52.     }
  53. }
  54.  
  55. void computeL() {
  56.     L.resize(n + 1);
  57.     int l0 = 1;
  58.     for (int i = 1; i <= n; i++) {
  59.         while (l0 <= i && R[l0] < i) {
  60.             l0++;
  61.         }
  62.         L[i] = l0;
  63.     }
  64. }
  65.  
  66. void solve() {
  67.     dp.assign(n + 1, vector<ll>(m + 1, -INF));
  68.     for (int i = 0; i <= n; i++) {
  69.         dp[i][0] = 0;
  70.     }
  71.     for (int j = 1; j <= m; j++) {
  72.         deque<int> dq;
  73.         for (int i = 1; i <= n; i++) {
  74.             while (!dq.empty() && dq.front() < L[i]) {
  75.                 dq.pop_front();
  76.             }
  77.             if (dp[i - 1][j - 1] != -INF) {
  78.                 ll g_i = dp[i - 1][j - 1] - i + 1;
  79.                 while (!dq.empty()) {
  80.                     int last = dq.back();
  81.                     ll g_last = dp[last - 1][j - 1] - last + 1;
  82.                     if (g_last <= g_i) {
  83.                         dq.pop_back();
  84.                     } else {
  85.                         break;
  86.                     }
  87.                 }
  88.                 dq.push_back(i);
  89.             }
  90.             ll best = -INF;
  91.             if (!dq.empty()) {
  92.                 int l0 = dq.front();
  93.                 best = dp[l0 - 1][j - 1] - l0 + 1 + i;
  94.             }
  95.             dp[i][j] = max(dp[i - 1][j], best);
  96.         }
  97.     }
  98.     ll ans = dp[n][m];
  99.     if (ans < 0) ans = 0;
  100.     cout << ans << endl;
  101. }
  102.  
  103. int main() {
  104.     freopen("PERFECT.inp", "r", stdin);
  105.     freopen("PERFECT.out", "w", stdout);
  106.     ios_base::sync_with_stdio(false);
  107.     cin.tie(0);
  108.     cin >> n >> k >> m;
  109.     a.resize(n + 1);
  110.     for (int i = 1; i <= n; i++) {
  111.         cin >> a[i];
  112.     }
  113.     computeR();
  114.     computeL();
  115.     solve();
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oFIinh
language:
C++14 (gcc 8.3)
created:
121 days 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!