CCCPaste

Untitled

#include 
#include 

#include 
using namespace std;
const double EPS = 1e-7;
int classrooms, teachers;
double c[111], t[111];
int max_right_with_a_teacher[15][111];
double cost[15][111];
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[111][1 << 16];
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))) {
            int new_mask = (visited | (1 << i));
            if(is_A_less_than_B(cost[i][at], mid) and rec(max_right_with_a_teacher[i][at] , new_mask, mid)) {
                return dp[at][visited] = true;
            }
        }
    }
    return dp[at][visited] = false;
}
int main()
{
    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 it = j;
                while(it < classrooms and is_A_less_than_B(sum, mid)) {
                    if(is_A_less_than_B(sum + (c[it] / t[i]), mid)) {
                        sum += (c[it] / t[i]);
                        it++;
                    }
                    else {
                        break;
                    }
                }
                max_right_with_a_teacher[i][j] = it;
                cost[i][j] = sum;
            }
        }
        memset(dp, -1, sizeof dp);
        if(rec(0, 0, mid)) {
            R = mid;
        }
        else {
            L = mid;
        }
    }
    printf("%.6f\n", L);
    return 0;
}