Cod sursa(job #585878)

Utilizator vladiiIonescu Vlad vladii Data 30 aprilie 2011 12:24:45
Problema Fabrica Scor 28
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.47 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
#define maxn 100010
#define maxp 50010
#define inf 999999999

int N, A, B;
int tminA = 0, tminB = 0;
int tA[maxp], tB[maxp];

vector<int> times;
multiset<pair<int, int> > dupaA;
multiset<int> dupastinga;
multiset<pair<int, int> > dupadreapta;

int cmp(int a, int b) {
    return a > b;
}

int main() {
    FILE *f1=fopen("fabrica.in", "r"), *f2=fopen("fabrica.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d %d\n", &N, &A, &B);
    for(i=1; i<=A; i++) {
        fscanf(f1, "%d\n", &tA[i]);
        dupaA.insert( make_pair(0 + tA[i], tA[i]) );
    }
    for(i=1; i<=B; i++) {
        fscanf(f1, "%d\n", &tB[i]);
        dupastinga.insert(tB[i]);
    }

    int pas = N;
    while(pas) {
        multiset<pair<int, int> >::iterator it;
        it = dupaA.begin();

        int sum = (*it).first;
        int durata = (*it).second;
        times.push_back(sum);

        tminA = max(tminA, sum);

        dupaA.erase(it);
        dupaA.insert( make_pair(sum + durata, durata) );

        pas --;
    }

    fprintf(f2, "%d ", tminA);

    //sort(times.begin(), times.end(), cmp);

    //for(i=0; i<times.size(); i++) {
    //    cout<<times[i]<<" ";
    //} cout<<endl;

    pas = 0;
    while(pas < N) {
        multiset<pair<int, int> >::iterator it;
        while(dupadreapta.size()) {
             it = dupadreapta.begin();

             if((*it).first <= times[pas]) {
                 int durata = (*it).second;

                 dupadreapta.erase(it);

                 dupastinga.insert(durata);
             }
             else {
                 break;
             }
        }

        //ma uit cind termin in stinga

        multiset<int>::iterator st;
        int finish1 = inf, finish2 = inf, durata;

        if(dupastinga.size()) {
            st = dupastinga.begin();
            finish1 = times[pas] + (*st);
        }

        if(dupadreapta.size()) {
            it = dupadreapta.begin();

            finish2 = (*it).first;
            durata = (*it).second;
        }

        if(finish1 < finish2) {
            dupadreapta.insert( make_pair(finish1, (*st)) );

            dupastinga.erase(st);
        }
        else {
            dupadreapta.erase(it);

            dupadreapta.insert( make_pair(finish2 + durata, durata) );
        }

        tminB = max(tminB, min(finish1, finish2));

        pas ++;
    }

    fprintf(f2, "%d\n", tminB);

    fclose(f1); fclose(f2);
    return 0;
}