Advertisement
Guest User

Untitled

a guest
May 20th, 2011
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.20 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <set>
  4. #include <map>
  5. #include <string>
  6. #include <string.h>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <math.h>
  10. #include <sstream>
  11. #include <complex>
  12. using namespace std;
  13.  
  14. void solve();
  15. #define mp make_pair
  16. #define pb push_back
  17. int main(){
  18. #ifdef DEBUG
  19.     freopen("input", "r", stdin);
  20.     //freopen("output","w",stdout);
  21. #endif
  22.     solve();
  23.     return 0;
  24. }
  25. typedef long long int li;
  26. #define int li
  27. typedef pair<int, int> pi;
  28. typedef vector<int> vi;
  29. typedef double ld;
  30.  
  31. struct sob{
  32.     int time;
  33.     bool type; //0-освобождение окна, true
  34.     int okno_type;
  35.     int id;
  36.     int cnt;
  37.     sob(int time,bool type,int okno_type,int id,int cnt){
  38.         this->time=time;
  39.         this->type=type;
  40.         this->okno_type=okno_type;
  41.         this->id=id;
  42.         this->cnt=cnt;
  43.     }
  44.     bool operator< (const sob& b){
  45.         return time<b.time || (time==b.time&& type<b.type) || (time==b.time && type==b.type && id<b.id) || (time==b.time && type==b.type && id== b.id && cnt<b.cnt);    
  46.     }
  47.     sob(){}
  48. };
  49. struct pq{
  50.     sob a[100000];
  51.     int cntt;
  52.     pq(){
  53.         cntt=0;
  54.     }
  55.     sob top(){
  56.         return a[1];
  57.     }
  58.     sob pop(){
  59.         swap(a[1],a[cntt--]);
  60.         down(1);
  61.     }
  62.     void down(int i){
  63.         if(2*i==cntt){
  64.             if(a[2*i]<a[i]){
  65.                 swap(a[i],a[2*i]);
  66.                 down(2*i);
  67.             }
  68.         }
  69.         else if(2*i<cntt){
  70.             int t=2*i;
  71.             if(a[t+1]<a[t])
  72.                 ++t;
  73.             if(a[t]<a[i]){
  74.                 swap(a[i],a[t]);
  75.                 down(t);
  76.             }
  77.         }
  78.     }
  79.     bool empty(){
  80.         return !cntt;
  81.     }
  82.     void up(int i){
  83.         if(i<2)
  84.             return;
  85.         if(a[i]<a[i/2]){
  86.             swap(a[i],a[i/2]);
  87.             up(i/2);
  88.         }
  89.     }
  90.     void push(const sob& b){
  91.         a[++cntt]=b;
  92.         up(cntt);
  93.     }
  94. };
  95. void solve(){
  96.     int k[3],t[3],cnt=0;    
  97.     for(int i=0;i<3;++i)
  98.         cin>>k[i];
  99.     for(int i=0;i<3;++i)
  100.         cin>>t[i];
  101.     int n;
  102.     int c[101010];
  103.     cin>>n;
  104.     for(int i=0;i<n;++i){
  105.         scanf("%I64d",c+i);
  106.     }
  107.     sort(c,c+n);
  108.     pq q;
  109.    
  110.     queue<int> wait[3];
  111.     for(int i=0;i<n;++i){
  112.         q.push(sob(c[i],true,0,i,cnt++));
  113.     }
  114.     int ans=0;
  115.     while(!q.empty()){
  116.         sob cur=q.top();
  117.         q.pop();
  118.         if(cur.type){
  119.             if(!k[cur.okno_type]){
  120.                 wait[cur.okno_type].push(cur.id);
  121.                 continue;
  122.             }
  123.             --k[cur.okno_type];
  124.             q.push(sob(cur.time+t[cur.okno_type],0,cur.okno_type,cur.id,cnt++));
  125.         }
  126.         else{
  127.             if(cur.okno_type==2){
  128.                 ans=max(ans,cur.time-c[cur.id]);
  129.             }
  130.             else{
  131.                 q.push(sob(cur.time,1,cur.okno_type+1,cur.id,cnt++));
  132.             }
  133.             if(wait[cur.okno_type].empty()){
  134.                 ++k[cur.okno_type];
  135.             }
  136.             else{
  137.                 q.push(sob(cur.time+t[cur.okno_type],0,cur.okno_type,wait[cur.okno_type].front(),cnt++));
  138.                 wait[cur.okno_type].pop();
  139.             };
  140.         }
  141.     }
  142.     cout<<ans;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement