#include "nile.h" //ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39] //Author: Sazid Hasan #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double dl; typedef vector<int> vi; typedef vector<vector<int>> vii; typedef vector<ll> vl; typedef vector<bool> vb; typedef pair<int,int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(a) a.begin(),a.end() #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define spc " " #ifdef ONLINE_JUDGE #define debarr(array) #define deb(x) #define del #else #define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl; #define deb(x) cerr << #x << " = " << x << endl; #define del cerr << '\n'; #endif const double PI = acos(-1); const int MOD = 1000000007; const int inf = (2147483647); vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { int n = W.size(); ll tot = accumulate(all(A), 0LL); vector<pll> arr = {{-1, 0}}; for(int i = 0; i < n; i++){ arr.push_back({W[i], A[i]-B[i]}); } sort(all(arr)); vl ans; for(auto x: E){ vl dp(n+1, 0); for(int i = 1; i <= n; i++){ dp[i] = dp[i-1]; for(int j = i-2; i-j <= 5 && j>=0 && (arr[i].ff-arr[j+1].ff)<=x; j--){ dp[i] = max(dp[i], dp[j] + arr[i].ss + arr[j+1].ss); } } ans.push_back(tot-dp[n]); } return ans; }