Cod sursa(job #585646)

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

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

vector<int> times;
multiset<pair<int, int> > dupaA;
multiset<pair<int, int> > dupaB;


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]);
        dupaB.insert( make_pair(0 + tB[i], 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);

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

        int sum = (*it).first;
        int durata = (*it).second;
        int momliber = sum - durata;

        dupaB.erase(it);

        if(momliber <= times[pas]) {
            tminB = max(tminB, times[pas] + durata);

            dupaB.insert( make_pair(times[pas] + durata + durata, durata) );
        }
        else {
            tminB = max(tminB, momliber + durata);

            dupaB.insert( make_pair(momliber + durata + durata, durata) );
        }

        pas ++;
    }

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

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