Language: C++

#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define pb         push_back
#define ALL(C)    (C).begin(),(C).end()

typedef long long ll;

const int N = 100;
const int M = 10000;
const int dinf=2000;
const ll inf = (1LL)<<50;

class Seat{
public:
  int a,b;
  ll time;
  bool operator<(const Seat & t)const{
    return a < t.a;
  }
};

void update(int &index,int &amax,int &amin,int &al,int &ar,
	    int i,int l,int r,int cap,int posl,int posr){
  if (l > r)swap(l,r);
  if (index==-1||
      (l>amin)||
      (l==amin&&r >amax)||
      (l==amin&&r==amax&&i < index)||
      (l==amin&&r==amax&&i==index&&posl<al)){
    index=i;
    amin=l;
    amax=r;
    al=posl;
    ar=posr;
  }
}

void makeupdate(int &index,int &amax,int &amin,int &al,int &ar,
		int tindex,int b,int a,int cap,int req){
  int tmp = a-b-1;
  if (tmp < req)return;
  int val=tmp-req;
  int l,r;
  l=val/2;r=val/2;
  // if (tmp%2 == 1 && req%2 == 0){
//     r++;
//   }
//   if (tmp%2 == 0 && req%2 == 1){
//     r++;
//   }

  if (val%2 == 1)r++;

  if (l+r+req != tmp){
    //cout << tindex <<" " << b<<" " << a << " " << l <<" " << r <<" " << req << " " << tmp << endl;
    assert(l+r+req == tmp);
  }

  update(index,amax,amin,al,ar,
	 tindex,l,r,cap,b+1+l,a-1-r);
}

void check(int cap,vector<Seat> &info,int req,int tindex,
	  int &index,int &amax,int &amin,int &al,int &ar){
  if (info.size() == 0){
    if (req > cap)return;
    update(index,amax,amin,al,ar,
	   tindex,dinf,dinf,cap,0,req-1);
    return;
  }
  
  if (info[0].a-req >=0){
    //cout <<"check " <<  info[0].a <<" " << req << endl;
    update(index,amax,amin,al,ar,
	   tindex,dinf,info[0].a-req,cap,0,req-1);
  }  

  rep(i,(int)info.size()-1){
    makeupdate(index,amax,amin,al,ar,
	       tindex,info[i].b,info[i+1].a,cap,req);
  }

  if (cap-req > info[info.size()-1].b){
    update(index,amax,amin,al,ar,
	   tindex,cap-req-info[info.size()-1].b-1,dinf,cap,cap-req,cap-1);
  }
}

void getseat(int &index,int &amax,int &amin,int &al,int &ar,
	     int n,vector<Seat> *a,int *cap,int req){
  rep(i,n){
    if (cap[i]>=req)check(cap[i],a[i],req,i,index,amax,amin,al,ar);
  }
}


double solve(int n,int *cap,ll cl,int m,ll *come,int *num,ll *wait,ll *eat){
  ll now=-1;
  int top=0;
  double sum=0,div=0;
  vector<Seat> seat[N];
  rep(i,m)div+=num[i];

  
  while(top < m){
    ll fast=inf;
    
    rep(i,n){
      rep(j,seat[i].size()){
	fast=min(fast,seat[i][j].time);
      }
    }
    
    if (now < come[top] && come[top] < fast){
      now=come[top];
    }else now = fast;

    //    cout << "update now " << now << endl;
    if (now >=cl)break;



    rep(i,n){
      rep(j,seat[i].size()){
	if (seat[i][j].time == now){
	  seat[i].erase(seat[i].begin()+j);
	  j--;
	}
      }
    }


//     rep(i,n){
//       rep(j,seat[i].size()){
//  	cout <<"seat info " <<i<<" " <<  seat[i][j].a <<" " << seat[i][j].b <<" " << seat[i][j].time<<endl;
//       }
//      }

       
    while(top < m){
      if (now == come[top]);
      else {
	while(top<m){
	  if (now > come[top]+wait[top]){
	    sum+=(-1)*num[top];
	  }else break;
	  top++;
	}
      }
      if (top == m || now < come[top])break;
      

      int index=-1,amax,amin,al,ar;
      getseat(index,amax,amin,al,ar,n,seat,cap,num[top]);
      if (index == -1)break;

      //cout << top <<" can sit " << index <<" from " << al <<" to " << ar << " " << now << " " << now+eat[top] << endl;
      
      seat[index].pb((Seat){al,ar,now+eat[top]});
      //      cout << seat[index].size()<<" " << now+eat[top] << endl;
      sort(ALL(seat[index]));
      sum+=((wait[top]-(now-come[top]))/(double)wait[top])*num[top];
      top++;
    }
  }
  REP(i,top,m)sum+=(-1)*num[i];
  return sum/div;
}

main(){
  int n,m;
  ll t;
  int cap[N];
  int num[M];
  ll come[M],wait[M],eat[M];
  while(cin>>n>>m>>t && n){
    rep(i,n)cin>>cap[i];
    rep(i,m)cin>>come[i]>>num[i]>>wait[i]>>eat[i];
    printf("%.16lf\n",solve(n,cap,t,m,come,num,wait,eat));
  }

  return false;
}


/*


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
0 0 0 x x x 4 4 4 7  7  7     2  2  2  8  8  8     3  3  3  9  9  9     1  1  1  
*/

Compiler output:
a.cc: In function 'void makeupdate(int&, int&, int&, int&, int&, int, int, int, int, int)':
a.cc:62:5: error: 'assert' was not declared in this scope
   62 |     assert(l+r+req == tmp);
      |     ^~~~~~
a.cc:6:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    5 | #include<algorithm>
  +++ |+#include <cassert>
    6 | using namespace std;
a.cc: At global scope:
a.cc:176:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  176 | main(){
      | ^~~~