Pagini recente » Cod sursa (job #1540872) | Cod sursa (job #2532954) | Cod sursa (job #1317148) | Cod sursa (job #2781134) | Cod sursa (job #2427730)
#include <iostream>
#include <cstdio>
#include <queue>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000;
const int L = 50000;
int len, n, m;
int a[L], b[L];
struct Event
{
int type;
/// 1 => from a
/// 2 => from b
int time;
int rep;
};
bool operator < (Event a, Event b)
{
return a.time > b.time;
}
priority_queue <Event> q;
int t[N];
bool ok(int lim)
{
while ((int) q.size() > 0)
{
q.pop();
}
for (int i = 1; i <= len; i++)
{
q.push({1, t[i], 0});
}
for (int i = 1; i <= m; i++)
{
q.push({2, 0, b[i]});
}
priority_queue <int> av;
int solved = 0, waiting = 0;
while ((int) q.size() > 0 && solved < len)
{
auto it = q.top();
while ((int) av.size() > 0 && (ll) (av.top() + it.time) > (ll) lim)
{
av.pop();
}
q.pop();
/// cout << it.time << "\n";
if (it.type == 1)
{
// cout << it.time << " " << (int) av.size() << "\n";
if ((int) av.size() == 0)
{
waiting++;
}
else
{
solved++;
q.push({2, it.time + av.top(), av.top()});
av.pop();
}
}
else
{
av.push(it.rep);
while ((int) av.size() > 0 && (ll) (av.top() + it.time) > (ll) lim)
{
av.pop();
}
if (waiting && (int) av.size() > 0)
{
q.push({2, it.time + av.top(), av.top()});
av.pop();
waiting--;
solved++;
}
}
}
//cout << "\n";
//cout << solved << " " << waiting << "\n";
return (solved == len && waiting == 0);
}
int main()
{
freopen ("fabrica.in", "r", stdin);
freopen ("fabrica.out", "w", stdout);
cin >> len >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
q.push({1, a[i], a[i]});
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
}
for (int i = 1; i <= len; i++)
{
auto it = q.top();
q.pop();
t[i] = it.time;
q.push({1, it.time + it.rep, it.rep});
}
//cout << ok(2) << "\n";
//return 0;
int r = 0, step = (1 << 29);
while (step > 0)
{
if (ok(r + step) == 0)
{
r += step;
}
step /= 2;
}
r++;
cout << t[len] << " " << r << "\n";
return 0;
}