Advertisement
Josif_tepe

Untitled

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