// This runs in linear time in O(T) where t is the maximum starting time #include #include using namespace std; #define MAX_N 10000 #define MAX_T 1000000 struct hearing { int s,a,b; }; hearing sched[MAX_N]; double opt[2+MAX_T]; // last meaningful start time is MAX_T; anything beyond that is exp=0 double sum[2+MAX_T]; // sum[k] = sum of opt[k]..opt[MAX_T] int main(int argc, const char * argv[]) { int n; cin >> n; for (int j=0; j < n; j++) { int s,a,b; cin >> sched[j].s >> sched[j].a >> sched[j].b; } int h = n-1; sum[MAX_T+1] = opt[MAX_T+1] = 0; for (int t=MAX_T; t >= 1; t--) { // first compute opt[t] opt[t] = opt[t+1]; // could always just wait while (h >= 0 && sched[h].s == t) { int a(sched[h].a), b(sched[h].b); double rest = (sum[min(t+a,MAX_T+1)] - sum[min(t+b+1,MAX_T+1)])/(b-a+1); double possible = 1 + rest; opt[t] = max(opt[t], possible); if (argc > 1) { // DEBUG MODE cerr << "If we choose to go to hearing " << h << " opt from there is " << possible << endl; cerr << "Opt at start time of " << h << " is " << opt[t] << endl; } h--; } // now compute sum[t] sum[t] = opt[t] + sum[t+1]; } cout << fixed << setprecision(9) << opt[1] << endl; }