Pagini recente » Cod sursa (job #433579) | Borderou de evaluare (job #1006483) | Cod sursa (job #1090822) | Borderou de evaluare (job #2742461) | Cod sursa (job #2651662)
#include <bits/stdc++.h>
#define MAX 131072
#define MOD 1000000007
#define INF 2100000000
#define eps 1e-5
using namespace std;
const int NMAX = 100100;
struct obj{
int val;
int index;
bool operator<(const obj &a) const{
if(val != a.val)
return val > a.val;
return index > a.index;
}
};
int N;
int nr[2], tma[NMAX];
int v[2][NMAX], val[2][NMAX];
priority_queue <obj> Q, revQ;
void read(){
scanf("%d%d%d", &N, &nr[0], &nr[1]);
for(int i = 1; i <= nr[0]; i++)
scanf("%d", &v[0][i]);
for(int i = 1; i <= nr[1]; i++)
scanf("%d", &v[1][i]);
sort(v[0] + 1, v[0] + nr[0] + 1);
sort(v[1] + 1, v[1] + nr[1] + 1);
}
void solve(int idx){
while(!Q.empty())
Q.pop();
while(!revQ.empty())
revQ.pop();
for(int i = 1; i <= nr[idx]; i++){
tma[i] = v[idx][i];
Q.push({tma[i], i});
revQ.push({-tma[i], i});
}
int rest = N - nr[idx], cnt = N, p = 0;
while(cnt){
int x = Q.top().val;
while(x == Q.top().val && cnt){
int a = Q.top().index;
val[idx][++p] = x;
Q.pop();
while(!revQ.empty() && tma[revQ.top().index] != -revQ.top().val)
revQ.pop();
if(rest){
tma[a] = x + v[idx][a];
Q.push({tma[a], a});
revQ.push({-tma[a], a});
--rest;
} else if(-revQ.top().val > x + v[idx][a]){
tma[a] = x + v[idx][a];
Q.push({tma[a], a});
revQ.pop();
revQ.push({-tma[a], a});
}
--cnt;
}
}
}
int main(){
freopen("fabrica.in", "r", stdin);
freopen("fabrica.out", "w", stdout);
read();
solve(0);
solve(1);
int ans = 0;
printf("%d ", val[0][N]);
for(int i = 1; i <= N; i++)
ans = max(ans, val[0][i] + val[1][N - i + 1]);
printf("%d", ans);
return 0;
}