Advertisement
Josif_tepe

Untitled

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