Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#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; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)