Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- struct jeg
- {
- ld first;
- int second;
- };
- const int N = 2000 + 7;
- int n;
- int a;
- int b;
- ld p1[N];
- ld p2[N];
- jeg best[N][N]; /// poz
- bool bigger(jeg a, jeg b)
- {
- if (a.first != b.first)
- return a.first > b.first;
- else
- return a.second < b.second;
- }
- jeg max(jeg a, jeg b)
- {
- if (bigger(a, b))
- return a;
- else
- return b;
- }
- void compute(ld c)
- {
- for (int i = 1; i <= n; i++)
- {
- for (int x = 0; x <= a; x++)
- {
- jeg one;
- jeg two;
- /// nu iau b
- /// nu iau a
- one = best[i - 1][x];
- /// iau a
- if (x >= 1)
- one = max(one, {best[i - 1][x - 1].first + p1[i], best[i - 1][x - 1].second});
- /// iau b
- /// nu iau a
- two = {best[i - 1][x].first + c + p2[i], best[i - 1][x].second + 1};
- /// iau a
- if (x >= 1)
- two = max(two, {best[i - 1][x - 1].first + c + p2[i] + p1[i] - p1[i] * p2[i], best[i - 1][x].second + 1});
- if (x == 0)
- best[i][x] = one;
- else
- {
- best[i][x] = max(two, one);
- }
- }
- }
- }
- ld solve()
- {
- compute(0);
- /** for (int i = 1; i <= n; i++)
- {
- for (int x = 0; x <= a; x++)
- {
- cout << i << " " << x << " : " << best[i][x].first << "\n";
- }
- }
- exit(0);**/
- ld l = - (ld) 1e9;
- ld r = + (ld) 1e9;
- for (int i = 1; i <= 200; i++)
- {
- ld mid = (l + r) * 0.5;
- compute(mid);
- if (best[n][a].second <= b)
- l = mid;
- else
- r = mid;
- }
- compute(l);
- return {best[n][a].first - l * best[n][a].second};
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- // freopen ("input", "r", stdin);
- cin >> n >> a >> b;
- for (int i = 1; i <= n; i++)
- cin >> p1[i];
- for (int i = 1; i <= n; i++)
- cin >> p2[i];
- cout << fixed << setprecision(6) << solve() << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement