Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef ABC
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <string>
- #include <map>
- #include <vector>
- #include <algorithm>
- #include <math.h>
- #include <set>
- #include <queue>
- #include <stack>
- #include <list>
- #define endl '\n'
- #define ABS(x) (((x)^((x) >> 31)) - ((x) >> 31))
- #include <ctime>
- using namespace std;
- typedef long long ll;
- typedef pair<ll, ll> pi;
- typedef pair<pi, ll> ppi;
- typedef vector<ll> vi;
- typedef vector<vi> vvi;
- typedef vector<pi> vpi;
- typedef vector<vpi> vvpi;
- typedef vector<ppi> vppi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef map<ll, ll> mii;
- typedef set<pi> spi;
- typedef set<ll> si;
- typedef multiset<ll> msi;
- typedef multiset<pi> mspi;
- typedef vector<si> vsi;
- template <typename T> using V = vector<T>;
- template <typename T> using VV = vector<V<T>>;
- template <typename T> using Mi = map<ll, T>;
- template <typename T> using MMi = map<ll, Mi<T>>;
- const double PI = 3.141592653589793238463;
- template < typename T >
- istream& operator>> (istream &cin, V<T> &arr) {
- for (T &val : arr) {
- cin >> val;
- }
- return cin;
- }
- template < typename T >
- ostream& operator<< (ostream &cout, VV<T> &arr) {
- for (V<T> &val : arr) {
- cout << val << endl;
- }
- return cout;
- }
- template < typename T >
- ostream& operator<< (ostream &cout, V<T> &arr) {
- for (T &val : arr) {
- cout << val << " ";
- }
- return cout;
- }
- template < typename T, typename R>
- istream& operator>> (istream &cin, pair<T, R> &p) {
- cin >> p.first >> p.second;
- return cin;
- }
- template < typename T, typename R>
- ostream& operator<< (ostream &cout, pair<T, R> &p) {
- cout << p.first << " " << p.second;
- return cout;
- }
- template < typename T >
- V<T>& operator--(V<T> &arr) {
- for (T &val : arr) {
- val--;
- }
- return arr;
- }
- template < typename T >
- V<T>& operator++(V<T> &arr) {
- for (T &val : arr) {
- val++;
- }
- return arr;
- }
- #endif // ABC
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- //cout.precision(15);
- //cout << fixed;
- //freopen("ancestor.in", "r", stdin);
- //freopen("ancestor.out", "w", stdout);
- ll n;
- cin >> n;
- vi a(n);
- cin >> a;
- ll W;
- cin >> W;
- vvb dp(n+1, vb(W+1));
- dp[0][0] = true;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j <= W; j++) {
- dp[i + 1][j] = dp[i][j];
- if (j >= a[i]) {
- dp[i + 1][j] = dp[i + 1][j] || dp[i][j - a[i]];
- }
- }
- }
- VV<double> ansdp(n + 1, V<double>(W+1,-1));
- ansdp[0][0] = 0;
- for (int i = 0; i < n; i++) {
- vi prefix(W + 2, 0);
- for (int j = 0; j <= W; j++) {
- prefix[j + 1] = prefix[j];
- if (dp[i][j]) {
- prefix[j + 1]++;
- }
- }
- for (int j = 0; j <= W; j++) {
- ansdp[i + 1][j] = ansdp[i][j];
- if (j >= a[i]) {
- ansdp[i + 1][j] = max(ansdp[i + 1][j], ansdp[i][j - a[i]]);
- }
- /////////////////
- double factor = 0.2;
- ll r = j;
- ll l = max(0,j - (int)(a[i] * factor));
- double modul = a[i] * factor - (int)(a[i] * factor);
- if (modul == 0) {
- modul = 1;
- l++;
- }
- ll sum = prefix[r + 1] - prefix[l+1];
- if (sum > 0) {
- ansdp[i + 1][j] = max(ansdp[i + 1][j], 1.0);
- }
- if (dp[i][l]) {
- ansdp[i + 1][j] = max(ansdp[i + 1][j], modul);
- }
- //////////////////
- factor = 0.8;
- l = max(0ll,j - a[i]);
- r = j - (a[i] * factor);
- if (r >= 0) {
- sum = prefix[r + 1] - prefix[l+1];
- if (sum > 0) {
- ansdp[i + 1][j] = max(ansdp[i + 1][j], 1.0);
- }
- if (dp[i][l]) {
- ansdp[i + 1][j] = max(ansdp[i + 1][j], 0.0);
- }
- }
- }
- }
- double ans = 0;
- for (int i = 0; i <= W; i++) {
- if (ansdp[n][i] >=0) {
- ans = max(ans, ansdp[n][i] + i);
- }
- }
- cout << min(ans, (double)W);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment