Guest User

Untitled

a guest
Aug 27th, 2019
738
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.68 KB | None | 0 0
  1. #ifndef ABC
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <iostream>
  4. #include <string>
  5. #include <map>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <math.h>
  9. #include <set>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #define endl '\n'
  14. #define ABS(x) (((x)^((x) >> 31)) - ((x) >> 31))
  15. #include <ctime>
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19. typedef pair<ll, ll> pi;
  20. typedef pair<pi, ll> ppi;
  21. typedef vector<ll> vi;
  22. typedef vector<vi> vvi;
  23. typedef vector<pi> vpi;
  24. typedef vector<vpi> vvpi;
  25. typedef vector<ppi> vppi;
  26. typedef vector<bool> vb;
  27. typedef vector<vb> vvb;
  28. typedef map<ll, ll> mii;
  29. typedef set<pi> spi;
  30. typedef set<ll> si;
  31. typedef multiset<ll> msi;
  32. typedef multiset<pi> mspi;
  33. typedef vector<si> vsi;
  34. template <typename T> using V = vector<T>;
  35. template <typename T> using VV = vector<V<T>>;
  36. template <typename T> using Mi = map<ll, T>;
  37. template <typename T> using MMi = map<ll, Mi<T>>;
  38.  
  39. const double PI = 3.141592653589793238463;
  40.  
  41.  
  42.  
  43. template < typename T >
  44. istream& operator>> (istream &cin, V<T> &arr) {
  45.     for (T &val : arr) {
  46.         cin >> val;
  47.     }
  48.     return cin;
  49. }
  50. template < typename T >
  51. ostream& operator<< (ostream &cout, VV<T> &arr) {
  52.     for (V<T> &val : arr) {
  53.         cout << val << endl;
  54.     }
  55.     return cout;
  56. }
  57. template < typename T >
  58. ostream& operator<< (ostream &cout, V<T> &arr) {
  59.     for (T &val : arr) {
  60.         cout << val << " ";
  61.     }
  62.     return cout;
  63. }
  64. template < typename T, typename R>
  65. istream& operator>> (istream &cin, pair<T, R> &p) {
  66.     cin >> p.first >> p.second;
  67.     return cin;
  68. }
  69. template < typename T, typename R>
  70. ostream& operator<< (ostream &cout, pair<T, R> &p) {
  71.     cout << p.first << " " << p.second;
  72.     return cout;
  73. }
  74.  
  75. template < typename T >
  76. V<T>& operator--(V<T> &arr) {
  77.     for (T &val : arr) {
  78.         val--;
  79.     }
  80.     return arr;
  81. }
  82. template < typename T >
  83. V<T>& operator++(V<T> &arr) {
  84.     for (T &val : arr) {
  85.         val++;
  86.     }
  87.     return arr;
  88. }
  89.  
  90.  
  91. #endif // ABC
  92.  
  93.  
  94.  
  95. int main() {
  96.  
  97.  
  98.     ios_base::sync_with_stdio(false);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101.     //cout.precision(15);
  102.     //cout << fixed;
  103.     //freopen("ancestor.in", "r", stdin);
  104.     //freopen("ancestor.out", "w", stdout);
  105.  
  106.     ll n;
  107.     cin >> n;
  108.     vi a(n);
  109.     cin >> a;
  110.     ll W;
  111.     cin >> W;
  112.  
  113.     vvb dp(n+1, vb(W+1));
  114.     dp[0][0] = true;
  115.     for (int i = 0; i < n; i++) {
  116.         for (int j = 0; j <= W; j++) {
  117.             dp[i + 1][j] = dp[i][j];
  118.             if (j >= a[i]) {
  119.                 dp[i + 1][j] = dp[i + 1][j] || dp[i][j - a[i]];
  120.             }
  121.         }
  122.     }
  123.     VV<double> ansdp(n + 1, V<double>(W+1,-1));
  124.     ansdp[0][0] = 0;
  125.    
  126.     for (int i = 0; i < n; i++) {
  127.         vi prefix(W + 2, 0);
  128.         for (int j = 0; j <= W; j++) {
  129.             prefix[j + 1] = prefix[j];
  130.             if (dp[i][j]) {
  131.                 prefix[j + 1]++;
  132.             }
  133.         }
  134.         for (int j = 0; j <= W; j++) {
  135.             ansdp[i + 1][j] = ansdp[i][j];
  136.             if (j >= a[i]) {
  137.                 ansdp[i + 1][j] = max(ansdp[i + 1][j], ansdp[i][j - a[i]]);
  138.             }
  139.  
  140.             /////////////////
  141.             double factor = 0.2;
  142.             ll r = j;
  143.             ll l = max(0,j - (int)(a[i] * factor));
  144.             double modul = a[i] * factor - (int)(a[i] * factor);
  145.             if (modul == 0) {
  146.                 modul = 1;
  147.                 l++;
  148.             }
  149.             ll sum = prefix[r + 1] - prefix[l+1];
  150.             if (sum > 0) {
  151.                 ansdp[i + 1][j] = max(ansdp[i + 1][j], 1.0);
  152.             }
  153.             if (dp[i][l]) {
  154.                 ansdp[i + 1][j] = max(ansdp[i + 1][j], modul);
  155.             }
  156.             //////////////////
  157.             factor = 0.8;
  158.             l = max(0ll,j - a[i]);
  159.             r = j - (a[i] * factor);
  160.             if (r >= 0) {
  161.                 sum = prefix[r + 1] - prefix[l+1];
  162.                 if (sum > 0) {
  163.                     ansdp[i + 1][j] = max(ansdp[i + 1][j], 1.0);
  164.                 }
  165.                 if (dp[i][l]) {
  166.                     ansdp[i + 1][j] = max(ansdp[i + 1][j], 0.0);
  167.                 }
  168.             }          
  169.         }
  170.     }
  171.  
  172.     double ans = 0;
  173.     for (int i = 0; i <= W; i++) {
  174.         if (ansdp[n][i] >=0) {
  175.             ans = max(ans, ansdp[n][i] + i);
  176.         }
  177.        
  178.     }
  179.     cout << min(ans, (double)W);
  180.  
  181.     return 0;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment