Cod sursa(job #585998)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 30 aprilie 2011 13:08:03
Problema Fabrica Scor 60
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 1.44 kb
#include <cstdio>
#include <queue>

using namespace std;

struct timp
{
    int start,add;
};

struct cmp
{
    bool operator()(timp i,timp j)
    {
        return i.start+i.add>j.start+j.add;
    }
};

struct cmp2
{
    bool operator()(timp i,timp j)
    {
        return i.start<j.start;
    }
};

timp aux;
priority_queue <timp,vector <timp>,cmp> v;
priority_queue <timp,vector <timp>,cmp2> v2;
int z[100001],y[100001],n,a,b;

int makesol (int x)
{
    int i;
    while (!v2.empty()) v2.pop();
    for (i=1;i<=b;++i)
    {
        aux.start=x-y[i];
        aux.add=y[i];
        v2.push(aux);
    }
    for (i=n;i>0;--i)
    {
        aux=v2.top();
        if (aux.start<z[i])
            return 0;
        v2.pop();
        aux.start-=aux.add;
        v2.push(aux);
    }
    return 1;
}

int main()
{
    int sol,x,i;
    freopen("fabrica.in","r",stdin);
    freopen("fabrica.out","w",stdout);
    scanf("%d%d%d",&n,&a,&b);
    for (i=1;i<=a;++i)
    {
        scanf("%d",&x);
        aux.add=x;
        v.push(aux);
    }
    for (i=1;i<=b;++i)
        scanf("%d",&y[i]);
    for (i=1;i<=n;++i)
    {
        aux=v.top();
        z[i]+=aux.start+aux.add;
        v.pop();
        aux.start+=aux.add;
        v.push(aux);
    }
    printf("%d ",z[n]);
    sol=2147483647;
    for (x=1073741824;x>0;x>>=1)
        if (makesol(sol-x))
            sol-=x;
    printf("%d",sol);
    return 0;
}