Advertisement
Josif_tepe

Untitled

Nov 6th, 2022
670
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. const double EPS = 1e-7;
  7. int classrooms, teachers;
  8. double c[111], t[111];
  9. int max_right_with_a_teacher[15][111];
  10. double cost[15][111];
  11. bool is_A_less_than_B(double A, double B) {
  12.     if(A < B) {
  13.         return true;
  14.     }
  15.     if(fabs(A - B) < EPS) {
  16.         return true;
  17.     }
  18.     return false;
  19. }
  20. int dp[111][1 << 16];
  21. bool rec(int at, int visited, double &mid) {
  22.     if(at == classrooms) {
  23.         return true;
  24.     }
  25.     if(__builtin_popcount(visited) == teachers) {
  26.         return false;
  27.     }
  28.     if(dp[at][visited] != -1) {
  29.         return dp[at][visited];
  30.     }
  31.     for(int i = 0; i < teachers; i++) {
  32.         if(!(visited & (1 << i))) {
  33.             int new_mask = (visited | (1 << i));
  34.             if(is_A_less_than_B(cost[i][at], mid) and rec(max_right_with_a_teacher[i][at] , new_mask, mid)) {
  35.                 return dp[at][visited] = true;
  36.             }
  37.         }
  38.     }
  39.     return dp[at][visited] = false;
  40. }
  41. int main()
  42. {
  43.     cin >> classrooms >> teachers;
  44.     for(int i = 0; i < classrooms; i++) {
  45.         cin >> c[i];
  46.     }
  47.    
  48.     for(int i = 0; i < teachers; i++) {
  49.         cin >> t[i];
  50.     }
  51.    
  52.     double L = 0.0, R = 2000000.0;
  53.     while(fabs(L - R) > EPS) {
  54.         double mid = L + (R - L) / 2.0;
  55.         for(int i = 0; i < teachers; i++) {
  56.             for(int j = 0; j < classrooms; j++) {
  57.                 double sum = 0.0;
  58.                 int it = j;
  59.                 while(it < classrooms and is_A_less_than_B(sum, mid)) {
  60.                     if(is_A_less_than_B(sum + (c[it] / t[i]), mid)) {
  61.                         sum += (c[it] / t[i]);
  62.                         it++;
  63.                     }
  64.                     else {
  65.                         break;
  66.                     }
  67.                 }
  68.                 max_right_with_a_teacher[i][j] = it;
  69.                 cost[i][j] = sum;
  70.             }
  71.         }
  72.         memset(dp, -1, sizeof dp);
  73.         if(rec(0, 0, mid)) {
  74.             R = mid;
  75.         }
  76.         else {
  77.             L = mid;
  78.         }
  79.     }
  80.     printf("%.6f\n", L);
  81.     return 0;
  82. }
  83.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement