Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 105;
- const double EPS = 1e-7;
- int classrooms, teachers;
- double c[maxn], t[maxn];
- int max_taken_with_a_teacher[maxn][maxn];
- 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[maxn][1 << 14];
- 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))) {
- if(rec(max_taken_with_a_teacher[i][at], (visited | (1 << i)), mid)) {
- return dp[at][visited] = true;
- }
- }
- }
- return dp[at][visited] = false;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- 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 k = j;
- while(k < classrooms and is_A_less_than_B(sum, mid)) {
- if(is_A_less_than_B(sum + (c[k] / t[i]), mid)) {
- sum += (c[k] / t[i]);
- k++;
- }
- else {
- break;
- }
- }
- max_taken_with_a_teacher[i][j] = k;
- }
- }
- memset(dp, -1, sizeof dp);
- if(rec(0, 0, mid)) {
- R = mid;
- }
- else {
- L = mid;
- }
- }
- printf("%.6lf\n", L);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement