SHARE
TWEET

Untitled

a guest Dec 3rd, 2018 170 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <string>
  11. #include <cassert>
  12. #include <bitset>
  13. #include <initializer_list>
  14. #include <unordered_map>
  15. #include <unordered_set>
  16.  
  17. using namespace std;
  18. typedef long long ll;
  19. typedef long double ld;
  20. int const INF = 1e9;
  21. ld const PI = acos(-1);
  22. ld const eps = 1e-7;
  23. ll const LLINF = 1e18;
  24. int const mod = 1e9 + 7;
  25. int const PH = 257;
  26.  
  27. namespace std {
  28.     template <typename U, typename V>
  29.     struct hash<std::pair<U, V>> {
  30.         std::size_t operator ()(std::pair<U, V> const& a) const {
  31.             using std::hash;
  32.             using std::size_t;
  33.             return size_t((1LL * hash<U>()(a.first) * PH + hash<V>()(a.second)) % mod);
  34.         }
  35.     };
  36. }
  37.  
  38. inline ll randll() {
  39.     ll res = rand();
  40.     for (int i = 0; i < 3; i++) {
  41.         res <<= 16;
  42.         res += rand();
  43.     }
  44.     return res;
  45. }
  46.  
  47. inline ld log(ld a, ld b) {
  48.     return (log(b) / log(a));
  49. }
  50.  
  51. int const N = 1010;
  52.  
  53. ll dp[2][3][N][N];
  54.  
  55. int main() {
  56. #ifdef _DEBUG
  57.     freopen("input.txt", "r", stdin);
  58.     freopen("output.txt", "w", stdout);
  59. #endif // _DEBUG
  60.     ios::sync_with_stdio(0);
  61.     int n, s, v;
  62.     cin >> n >> s >> v;
  63.     vector <ll> f(n + 1, 0);
  64.     for (int i = 1; i < n; i++) cin >> f[i];
  65.     vector <int> w = { 0, s % v, v };
  66.     int cnt = s / v;
  67.     for (int k = 0; k < 2; k++) for (int last = 0; last < 3; last++) for (int i = 0; i <= n; i++) for (int j = 0; j <= cnt; j++) dp[k][last][i][j] = LLINF;
  68.     dp[0][0][0][0] = 0;
  69.     for (int i = 0; i < n; i++) for (int j = 0; j <= cnt; j++) for (int k = 0; k < 2; k++) for (int last = 0; last < 3; last++) {
  70.         dp[k][0][i + 1][j] = min(dp[k][0][i + 1][j], dp[k][last][i][j]);
  71.         if (!k && w[1]) dp[1][1][i + 1][j] = min(dp[1][1][i + 1][j], dp[0][last][i][j] + f[i] * w[last] * w[1]);
  72.         if (j < cnt) dp[k][2][i + 1][j + 1] = min(dp[k][2][i + 1][j + 1], dp[k][last][i][j] + f[i] * w[last] * w[2]);
  73.     }
  74.     ll ans = LLINF;
  75.     for (int last = 0; last < 3; last++) ans = min(ans, dp[bool(w[1])][last][n][cnt]);
  76.     cout << ans;
  77.     return 0;
  78. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top