Salvens

H

Aug 4th, 2023
1,306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <array>
  6. #include <set>
  7. #include <map>
  8. #include <deque>
  9.  
  10. using namespace std;
  11.  
  12. //#define int long long
  13. #pragma comment(linker,"/STACK:1000000000,1000000000")
  14.  
  15. const int INF = 1e9 + 7;
  16. const int MAXN = 20010;
  17. const int N = 1e5 + 10;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void init_dp(vector<vector<int>>& dp) {
  21.     for (int i = 0; i < dp.size(); ++i) {
  22.         for (int j = 0; j < dp[i].size(); ++j) {
  23.             dp[i][j] = INF;
  24.         }
  25.     }
  26. }
  27.  
  28. struct min_on_window {
  29.     deque<pair<int, int>> d;
  30.  
  31.     void push(int x, int ind) {
  32.         while (!d.empty() && d.back().first >= x) {
  33.             d.pop_back();
  34.         }
  35.         d.emplace_back(x, ind);
  36.     }
  37.  
  38.     void pop(int ind) {
  39.         if (!d.empty() && d.front().second == ind) {
  40.             d.pop_front();
  41.         }
  42.     }
  43.  
  44.     int get_min() {
  45.         return (d.empty() ? INF : d.front().first);
  46.     }
  47. };
  48.  
  49. signed main() {
  50.     ios_base::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.     cout.tie(nullptr);
  53.  
  54.     int n, w, l, min_r, max_r;
  55.     cin >> n >> w >> l >> min_r >> max_r;
  56.     vector<int> a(l + 1), pref_sum(l + 1);
  57.     pref_sum[0] = 0;
  58.     for (int i = 1; i <= l; ++i) {
  59.         cin >> a[i];
  60.         pref_sum[i] = pref_sum[i - 1] + a[i];
  61.     }
  62.  
  63.     vector<min_on_window> mini(n + 1);
  64.     vector<vector<int>> dp(l + 1, vector<int>(n + 1));
  65.     init_dp(dp);
  66.     for (int i = min_r + w; i <= l - min_r; ++i) {
  67.         for (int j = 0; j <= n; ++j) {
  68.             mini[j].push(dp[i - w - min_r][j], i - w - min_r);
  69.             if (i - w - max_r - 1 >= 0) {
  70.                 mini[j].pop(i - w - max_r - 1);
  71.             }
  72.         }
  73.  
  74.         if (i - w <= max_r) {
  75.             dp[i][1] = pref_sum[i] - pref_sum[i - w];
  76.         }
  77.         for (int j = 2; j <= n; ++j) {
  78.             dp[i][j] = min(INF, pref_sum[i] - pref_sum[i - w] + mini[j - 1].get_min());
  79.         }
  80.     }
  81.  
  82.     int ans = INF;
  83.     for (int i = max(0, l - max_r); i <= l - min_r; ++i) {
  84.         ans = min(ans, dp[i][n]);
  85.     }
  86.     if (ans == INF) {
  87.         cout << "No solution.\n";
  88.     } else {
  89.         cout << ans << '\n';
  90.     }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment