Cod sursa(job #2651662)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 23 septembrie 2020 11:20:47
Problema Fabrica Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#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;
}