Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <bits/stdc++.h>
- using namespace std;
- const double EPS = 1e-7;
- int classrooms, teachers;
- double c[111], t[111];
- int max_right_with_a_teacher[15][111];
- double cost[15][111];
- bool is_A_less_than_B(double A, double B) {
- if(A < B) {
- return true;
- }
- if(fabs(A - B) < EPS) {
- return true;
- }
- return false;
- }
- int dp[111][1 << 16];
- bool rec(int at, int visited, double &mid) {
- if(at == classrooms) {
- return true;
- }
- if(__builtin_popcount(visited) == teachers) {
- return false;
- }
- if(dp[at][visited] != -1) {
- return dp[at][visited];
- }
- for(int i = 0; i < teachers; i++) {
- if(!(visited & (1 << i))) {
- int new_mask = (visited | (1 << i));
- if(is_A_less_than_B(cost[i][at], mid) and rec(max_right_with_a_teacher[i][at] , new_mask, mid)) {
- return dp[at][visited] = true;
- }
- }
- }
- return dp[at][visited] = false;
- }
- int main()
- {
- cin >> classrooms >> teachers;
- for(int i = 0; i < classrooms; i++) {
- cin >> c[i];
- }
- for(int i = 0; i < teachers; i++) {
- cin >> t[i];
- }
- double L = 0.0, R = 2000000.0;
- while(fabs(L - R) > EPS) {
- double mid = L + (R - L) / 2.0;
- for(int i = 0; i < teachers; i++) {
- for(int j = 0; j < classrooms; j++) {
- double sum = 0.0;
- int it = j;
- while(it < classrooms and is_A_less_than_B(sum, mid)) {
- if(is_A_less_than_B(sum + (c[it] / t[i]), mid)) {
- sum += (c[it] / t[i]);
- it++;
- }
- else {
- break;
- }
- }
- max_right_with_a_teacher[i][j] = it;
- cost[i][j] = sum;
- }
- }
- memset(dp, -1, sizeof dp);
- if(rec(0, 0, mid)) {
- R = mid;
- }
- else {
- L = mid;
- }
- }
- printf("%.6f\n", L);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement