Cod sursa(job #591676)

Utilizator desoComan Andrei deso Data 25 mai 2011 02:24:50
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define pb push_back
#define sz size()
#define LL long long
#define ULL unsigned long long
#define SORT(x) sort(x.begin(), x.end())
#define REVERSE(x) reverse(x.begin(), x.end())
#define REP(x, hi) for (int x=0; x<(hi); x++)
#define FOR(x, lo, hi) for (int x=(lo); x<(hi); x++)
#define INFILE ".in" 
#define OUTFILE ".out"
#define MAX 100100
ifstream fin (INFILE);
ofstream fout (OUTFILE);

vector<pair<unsigned long long, unsigned long long> > a, b;

unsigned long long aend[MAX], bend[MAX];
int n, na, nb;

bool comp(pair<ULL,ULL> x, pair<ULL,ULL> y)
{
  return (x.first) > (y.first);
}

void flow(vector<pair<ULL,ULL> > v, unsigned long long end[MAX])
{
  make_heap (v.begin(),v.end(),comp);
  for(int i=0; i<n; i++)
  {
    pair<ULL,ULL> aux = v[0];
    end[i] = aux.first;
    aux.first += aux.second;
    pop_heap(v.begin(), v.end(), comp);
    v[v.sz-1] = aux;
    push_heap(v.begin(), v.end(), comp);
  }
}

int main()
{
  fin >> n >> na >> nb;
  a.resize(na);
  b.resize(nb);
  unsigned long long aux;
  REP(i, na)
  {
    fin >> aux;
    a[i] = pair<ULL,ULL>(aux,aux);
  }
  REP(i, nb)
  {
    fin >> aux;
    b[i] = pair<ULL,ULL>(aux,aux);
  }

  flow(a, aend);
  flow(b, bend);
  ULL maxa = 0, maxb = 0;

  for(int i=0; i<n; i++)
  {
    maxa = max(maxa, aend[i]);
    maxb = max(maxb, aend[i] + bend[n-i-1]);
  }

  fout << maxa << " " << maxb << endl;
	
	return 0;
}