Cod sursa(job #586118)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 30 aprilie 2011 13:45:46
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 2.32 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "fabrica.in"
#define outfile "fabrica.out"
#define nrMax 50013
#define inf (~(1<<31))
#define ll long long

using namespace std;

vector <int> a;
vector <int> b;

vector <int> ea;
vector <int> sb;

int n;
ll ta, tb, tot;

vector <int> readVector(int n) {
  vector <int> v;
  for(int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    v.push_back(x);
  }
  return v;
}

void writeVector(vector <int> v) {
  for(unsigned i = 0; i < v.size(); ++i)
    printf("%d ", v[i]);
  printf("\n");
}

void read() {
  int nrA, nrB;
  scanf("%d %d %d\n", &n, &nrA, &nrB);
  a = readVector(nrA);
  b = readVector(nrB);
}

ll getBeers(vector <int> &v, int time) {
  ll sol = 0;
  //writeVector(v);
  for(unsigned i = 0; i < v.size(); ++i)
    sol += (time / v[i]);
  return sol;
}

ll getTime(vector <int> &v) {
  ll le = 1, ri = inf, mi;
  ll sol = inf;

  while(le <= ri) {
    mi = (le+ri)>>1;
    //printf("%lld %lld\n", mi, getBeers(v, mi));
    if(getBeers(v, mi) >= n) sol = mi, ri = mi-1;
    else le = mi+1;
  }

  return sol;
}

vector <int> getBeerTime(vector <int> &v, int time, int n, int deelay) {
  vector <int> w;
  for(unsigned i = 0; i < v.size() && n; ++i)
    for(int j = 1; (ll)j * v[i] <= time && n; ++j)
      --n, w.push_back((j-deelay) * v[i]);
  return w;
}

bool canStart(vector <int> &a, vector <int> &b, int time) {
  for(unsigned i = 0; i < a.size(); ++i)
    if(a[i] > (ll)b[i] + time)
      return false;
  return true;
}

void solve() {

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  writeVector(a);
  writeVector(b);

  ta = getTime(a);
  tb = getTime(b);

  //printf("%lld %lld \n", ta, tb);

  ea = getBeerTime(a, ta, n, 0); //get end time in A
  sb = getBeerTime(b, tb, n, 1); //get start time in B

  sort(ea.begin(), ea.end());
  sort(sb.begin(), sb.end());

  //writeVector(ea);
  //writeVector(sb);

  ll tsb = inf; // time start b
  ll le = 0, ri = inf, mi;

  while(le <= ri) {
    mi = (le+ri) >> 1;
    if(canStart(ea, sb, mi)) tsb = mi, ri = mi-1;
    else le = mi+1;
  }

  //printf("%lld %lld %lld\n", ta, tb, tsb);

  tot = tb + tsb;
}

void write() {
  printf("%lld %lld\n", ta, tot);
}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  read();
  solve();
  write();

  fclose(stdin);
  fclose(stdout);
  return 0;
}