p450.ans4
======================
-0.1428571428571428

=================
p450.ans3
======================
0.5542857142857143

=================
p450.ans2
======================
0.4285714285714285

=================
p450.ans5
======================
0.8000000000000000

=================
p450.in1
======================
1 4 100
7
10 1 50 50
15 2 50 50
25 1 50 50
35 3 50 50

=================
p450.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int inf = (int)2e9 + 42;

int n, m, t;
vector<int> cap, start, group_size, deadline, eat_time;

void read() {
    cin >> n >> m >> t;
    cap.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> cap[i];
    }

    start.resize(m);
    group_size.resize(m);
    deadline.resize(m);
    eat_time.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> start[i] >> group_size[i] >> deadline[i] >> eat_time[i];
    }
}

vector<vector<int>> cc;
vector<double> satisfaction;
vector<bool> seated;

struct Option {
    int min_dist;
    int max_dist;
    int idx;
    int pos;
};

vector<Option> opts;

priority_queue<
    pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>>
    ev;
queue<int> waiting;

bool is_better(const Option& a, const Option& b) {
    if(a.min_dist != b.min_dist) {
        return a.min_dist > b.min_dist;
    }
    if(a.max_dist != b.max_dist) {
        return a.max_dist > b.max_dist;
    }
    if(a.idx != b.idx) {
        return a.idx < b.idx;
    }
    return a.pos < b.pos;
}

bool can_seat(int g) {
    bool found = false;
    Option best_opt;

    for(int c = 0; c < n; c++) {
        int sum = 0;
        int last_left, last_right;

        for(int i = 0; i + group_size[g] <= cap[c]; i++) {
            if(i == 0) {
                for(int j = 0; j < group_size[g]; j++) {
                    sum += cc[c][j];
                }
                last_left = -1;
                last_right = group_size[g];
            } else {
                sum += cc[c][i + group_size[g] - 1] - cc[c][i - 1];
                if(cc[c][i - 1]) {
                    last_left = i - 1;
                }
                last_right = max(last_right, i + (int)group_size[g]);
            }
            while(last_right < cap[c] && !cc[c][last_right]) {
                last_right++;
            }

            if(!sum) {
                int left_span = (last_left == -1) ? inf : (i - 1 - last_left);
                int right_span = (last_right == cap[c])
                                     ? inf
                                     : (last_right - i - group_size[g]);
                Option cur_opt = {
                    min(left_span, right_span), max(left_span, right_span), c, i
                };

                if(!found || is_better(cur_opt, best_opt)) {
                    found = true;
                    best_opt = cur_opt;
                }
            }
        }
    }

    if(found) {
        opts[g] = best_opt;
        seated[g] = true;
        for(int i = 0; i < group_size[g]; i++) {
            cc[best_opt.idx][best_opt.pos + i] = 1;
        }
    }

    return found;
}

void remove_group(int g) {
    Option& opt = opts[g];
    for(int i = 0; i < group_size[g]; i++) {
        cc[opt.idx][opt.pos + i] = 0;
    }
}

void solve() {
    // The simulator is deterministic, so this is essentially an implementation
    // problem. We can notice that, constraints for N and C are tiny, so we
    // don't even need to implement operations with BSTs. In theory we
    // should be able to use a BST over empty ranges and one over
    // counters, and always find the largest empty interval which will be split
    // in half. However, for given constraints we don't really need this. We
    // can simply keep an event priority queue, and implement each leaving or
    // entering operation naively.

    cc.resize(n);
    for(int i = 0; i < n; i++) {
        cc[i].assign(cap[i], 0);
    }

    satisfaction.resize(m);
    opts.resize(m);
    seated.assign(m, false);

    for(int i = 0; i < m; i++) {
        satisfaction[i] = -1;
        ev.emplace(start[i], i);
        ev.emplace(start[i] + deadline[i], m);
    }

    while(!ev.empty()) {
        int64_t cur_time = ev.top().first;
        if(cur_time >= t) {
            break;
        }

        while(!ev.empty() && ev.top().first == cur_time) {
            int id = ev.top().second;
            ev.pop();

            if(id < 0) {
                remove_group(-id - 1);
            }
            if(id >= 0 && id < m) {
                waiting.push(id);
            }
        }

        while(!waiting.empty()) {
            int g = waiting.front();
            if(cur_time <= start[g] + deadline[g]) {
                if(can_seat(g)) {
                    ev.emplace(cur_time + eat_time[g], -(g + 1));
                    satisfaction[g] =
                        (double)(start[g] + deadline[g] - cur_time) /
                        deadline[g];
                    waiting.pop();
                    continue;
                }
            }
            if(cur_time >= start[g] + deadline[g]) {
                waiting.pop();
                continue;
            }
            break;
        }
    }

    int64_t tot_sz = 0;
    double tot = 0.0;
    for(int i = 0; i < m; i++) {
        tot += satisfaction[i] * group_size[i];
        tot_sz += group_size[i];
    }

    cout << fixed << setprecision(16) << tot / tot_sz << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p450.ans1
======================
0.7428571428571429

=================
p450.in2
======================
1 2 100
5
30 3 20 50
40 4 40 50

=================
p450.in5
======================
2 3 100
4 2
10 4 20 20
30 2 20 20
40 4 20 20

=================
p450.in4
======================
1 2 100
5
50 3 20 50
60 4 50 30

=================
p450.in3
======================
1 2 100
5
49 3 20 50
60 4 50 30

=================
statement.txt
======================
450. Ramen Shop
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Ron is a master of a ramen shop.

Recently, he has noticed some customers wait for a long time. This has been caused by lack of seats during lunch time. Customers loses their satisfaction if they wait for a long time, and some of them will even give up waiting and go away. For this reason, he has decided to increase seats in his shop. To determine how many seats are appropriate, he has asked you, an excellent programmer, to write a simulator of customer behavior.

Customers come to his shop in groups, each of which is associated with the following four parameters:
Ti: when the group comes to the shop
Pi: number of customers
Wi: how long the group can wait for their seats
Ei: how long the group takes for eating


The i-th group comes to the shop with Pi customers together at the time Ti. If Pi successive seats are available at that time, the group takes their seats immediately. Otherwise, they wait for such seats being available. When the group fails to take their seats within the time Wi (inclusive) from their coming and strictly before the closing time, they give up waiting and go away. In addition, if there are other groups waiting, the new group cannot take their seats until the earlier groups are taking seats or going away.

The shop has N counters numbered uniquely from 1 to N. The i-th counter has Ci seats. A group cannot spread over multiple counters. The group prefers "seats with a greater distance to the nearest group." Precisely, the group takes their seats according to the criteria listed below. For each block of seats of appropriate size within each counter, values SL and SR are calculated. Here, SL denotes the number of successive empty seats on the left side of the group after their seating, and SR the number on the right side. SL and SR are considered to be infinity if there are no other customers on the left side and on the right side respectively. Note that these numbers don't take into account people in other counters.
Prefers seats maximizing min { SL, SR }.
If there are multiple alternatives meeting the first criterion, prefers seats maximizing max { SL, SR }.
If there are still multiple alternatives, prefers the counter of the smallest number.
If there are still multiple alternatives, prefers the leftmost seats.

When multiple groups are leaving the shop at the same time and some other group is waiting for available seats, seat assignment for the waiting group should be made after all the finished groups leave the shop. If a customer starts eating, he is allowed to finish even after the shop closes.

Your task is to calculate the average satisfaction over customers. The satisfaction of a customer in the i-th group is given as follows:
If the group goes away without eating, -1.
Otherwise, (Wi - ti) / Wi where ti is the actual waiting time for the i-th group (the value ranges between 0 to 1 inclusive).


Input
The input has the following format:

N M T

C1 C2... CN

T1 P1 W1 E1

T2 P2 W2 E2

...

TM PM WM EM

N indicates the number of counters, M indicates the number of groups and T indicates the closing time. The shop always opens at the time 0. All input values are integers.

You can assume that 1 ≤ N ≤ 100, 1 ≤ M ≤ 10000, 1 ≤ T ≤ 109, 1 ≤ Ci ≤ 100, 0 ≤ T1 < T2 <... < TM < T, 1 ≤ Pi ≤ max{Ci}, 1 ≤ Wi ≤ 109 and 1 ≤ Ei ≤ 109.

Output
Output the average satisfaction over all customers in a line. The output value may be printed with an arbitrary number of fractional digits, but may not contain an absolute error greater than 10-9.

Example(s)
sample input
sample output
1 4 100
7
10 1 50 50
15 2 50 50
25 1 50 50
35 3 50 50
0.7428571428571429

sample input
sample output
1 2 100
5
30 3 20 50
40 4 40 50
0.4285714285714285

sample input
sample output
1 2 100
5
49 3 20 50
60 4 50 30
0.5542857142857143

sample input
sample output
1 2 100
5
50 3 20 50
60 4 50 30
-0.1428571428571428

sample input
sample output
2 3 100
4 2
10 4 20 20
30 2 20 20
40 4 20 20
0.8000000000000000



=================
