Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- //#include <bits/stdc++.h>
- #include <cstring>
- using namespace std;
- double c[105], t[105];
- const double EPS = 1e-9;
- int classrooms, teachers;
- bool is_a_less_than_b(double a, double b) {
- if(a < b) {
- return true;
- }
- if((a - b) < EPS) {
- return true;
- }
- return false;
- }
- int max_right_with_a_person[15][101];
- double cost[15][101];
- int dp[101][1 << 15];
- bool rec(int at, int visited, double &x) {
- 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], x) and rec(max_right_with_a_person[i][at], new_mask, x)) {
- return dp[at][visited] = true;
- }
- }
- }
- return dp[at][visited] = false;
- }
- int main() {
- cin >> classrooms >> teachers;
- for(int i = 0; i < classrooms; i++) {
- int o;
- cin >> o;
- c[i] = (double) o;
- }
- for(int i = 0; i < teachers; i++) {
- int o;
- cin >> o;
- t[i] = (double) o;
- }
- double L = 0.00;
- double R = 20000000.0;
- while(fabs(L - R) > EPS) {
- double x = L + (R - L) / 2.0;
- for(int i = 0; i < teachers; i++) {
- for(int j = 0; j < classrooms; j++) {
- int it = j;
- double p = 0.0;
- bool can = false;
- while(it < classrooms and is_a_less_than_b(p, x)) {
- if (is_a_less_than_b(p + (c[it] / t[i]), x)){
- p += (c[it] / t[i]);
- it++;
- can = true;
- }
- else {
- break;
- }
- }
- max_right_with_a_person[i][j] = it;
- cost[i][j] = p;
- }
- }
- // cout << x << endl;
- memset(dp, -1, sizeof dp);
- if(rec(0, 0, x)) {
- R = x;
- }
- else {
- L = x;
- }
- }
- printf("%.6f\n", L);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement