Cod sursa(job #585719)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 30 aprilie 2011 11:24:22
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 2.19 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("fabrica.in");
ofstream g("fabrica.out");

struct procesor{
    unsigned int dur;
};
struct procesor2{
    unsigned int dur;
    unsigned int unt;
    bool l;
};
struct compara{
    bool operator()(const procesor& x, const procesor& y) const {
         return (x.dur > y.dur);
  }
};
struct compara2{
    bool operator()(const procesor2& x, const procesor2& y) const {
         return (x.unt > y.unt);
  }
};
priority_queue<procesor, vector<procesor>, compara> qa;
priority_queue<procesor2, vector<procesor2>, compara2> qa2;
priority_queue<procesor, vector<procesor>, compara> qb;
priority_queue<procesor2, vector<procesor2>, compara2> qb2;

unsigned int n,i,nra,nrb,maxa,maxt,d,nrv;
procesor p;
procesor2 p2,v[100000];
int main () {
    f >> n >> nra >> nrb;
    p.dur=4294967295;
    qa.push(p);
    qb.push(p);
    for (i=1;i<=nra;i++) {
        f >> d;
        p.dur=d;
        qa.push(p);
    }
    for (i=1;i<=nrb;i++) {
        f >> d;
        p.dur=d;
        qb.push(p);
    }
    p2.dur=p2.unt=4294967295;p2.l=false;
    qa2.push(p2);
    qb2.push(p2);
    for (i=1;i<=n;i++) {
        p=qa.top();p2=qa2.top();
        if (p.dur<p2.dur+p2.unt) {
            qa.pop();
            p2.dur=p.dur;
            p2.unt=p2.dur;p2.l=false;qa2.push(p2);
            if (maxa<p2.unt) maxa=p2.unt;
        }
        else {
            p2.unt+=p2.dur;qa2.pop();qa2.push(p2);
            if (maxa<p2.unt) maxa=p2.unt;
        }
        p2=qa2.top();nrv=0;
        while (p2.l==true&&qa2.empty()==false) {
            nrv++;v[nrv]=p2;qa2.pop();p2=qa2.top();
        }
        p2.l=true;qa2.pop();qa2.push(p2);
        for (d=1;d<=nrv;d++) qa2.push(v[d]);
        d=p2.unt;p=qb.top();p2=qb2.top();
        if (p.dur<p2.dur+p2.unt) {
            qb.pop();
            p2.dur=p.dur;
            p2.unt=p2.dur;qb2.push(p2);
            if (maxt<p2.unt+d) maxt=p2.unt+d;
        }
        else {
            p2.unt+=p2.dur;qb2.pop();qb2.push(p2);
            if (maxt<p2.unt+d) maxt=p2.unt+d;
        }
    }
    g << maxa << ' ' << maxt << '\n';
    f.close();g.close();
    return 0;
}