Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <array>
- #include <set>
- #include <map>
- #include <deque>
- using namespace std;
- //#define int long long
- #pragma comment(linker,"/STACK:1000000000,1000000000")
- const int INF = 1e9 + 7;
- const int MAXN = 20010;
- const int N = 1e5 + 10;
- const int MOD = 1e9 + 7;
- void init_dp(vector<vector<int>>& dp) {
- for (int i = 0; i < dp.size(); ++i) {
- for (int j = 0; j < dp[i].size(); ++j) {
- dp[i][j] = INF;
- }
- }
- }
- struct min_on_window {
- deque<pair<int, int>> d;
- void push(int x, int ind) {
- while (!d.empty() && d.back().first >= x) {
- d.pop_back();
- }
- d.emplace_back(x, ind);
- }
- void pop(int ind) {
- if (!d.empty() && d.front().second == ind) {
- d.pop_front();
- }
- }
- int get_min() {
- return (d.empty() ? INF : d.front().first);
- }
- };
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, w, l, min_r, max_r;
- cin >> n >> w >> l >> min_r >> max_r;
- vector<int> a(l + 1), pref_sum(l + 1);
- pref_sum[0] = 0;
- for (int i = 1; i <= l; ++i) {
- cin >> a[i];
- pref_sum[i] = pref_sum[i - 1] + a[i];
- }
- vector<min_on_window> mini(n + 1);
- vector<vector<int>> dp(l + 1, vector<int>(n + 1));
- init_dp(dp);
- for (int i = min_r + w; i <= l - min_r; ++i) {
- for (int j = 0; j <= n; ++j) {
- mini[j].push(dp[i - w - min_r][j], i - w - min_r);
- if (i - w - max_r - 1 >= 0) {
- mini[j].pop(i - w - max_r - 1);
- }
- }
- if (i - w <= max_r) {
- dp[i][1] = pref_sum[i] - pref_sum[i - w];
- }
- for (int j = 2; j <= n; ++j) {
- dp[i][j] = min(INF, pref_sum[i] - pref_sum[i - w] + mini[j - 1].get_min());
- }
- }
- int ans = INF;
- for (int i = max(0, l - max_r); i <= l - min_r; ++i) {
- ans = min(ans, dp[i][n]);
- }
- if (ans == INF) {
- cout << "No solution.\n";
- } else {
- cout << ans << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment