Cod sursa(job #2651640)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 23 septembrie 2020 10:29:24
Problema Fabrica Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 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{
    long long val;
    int index;
    bool operator<(const obj &a) const{
        if(val != a.val)
            return val > a.val;
        return index > a.index;
    }
};

int N, nra, nrb;
int va[NMAX], vb[NMAX];
long long ansA, ansB;
long long tma[NMAX];
bool exist[NMAX];

priority_queue <obj> Q, revQ;

void read(){
    scanf("%d%d%d", &N, &nra, &nrb);
    for(int i = 1; i <= nra; i++)
        scanf("%d", &va[i]);
    for(int i = 1; i <= nrb; i++)
        scanf("%d", &vb[i]);
    sort(va + 1, va + nra + 1);
    sort(vb + 1, vb + nrb + 1);
    for(int i = 1; i <= nra; i++){
        Q.push({va[i], i});
        revQ.push({-va[i], i});
        tma[i] = va[i];
    }
}

void brute(){
    int nr = 0;
    for(int i = 1; i <= 4000 && nr < N; i++){
        bool showI = false;
        for(int j = 1; j <= nra && nr < N; j++){
            if(i % va[j] == 0){
                if(!showI){
                    printf("%d : ", i);
                    showI = true;
                }
                printf("%d ", va[j]);
                nr++;
            }
        }
        if(showI)
            printf("\n");
    }
}

int main(){

    freopen("fabrica.in", "r", stdin);
    freopen("fabrica.out", "w", stdout);

    read();
    //brute();

    int idx = nra, rest = N - nra, cnt = N;
    while(cnt){
        long long x = Q.top().val;
        //printf("%lld : ", x);
        while(x == Q.top().val && cnt){
            int a = Q.top().index;
            //printf("%lld ", va[a]);
            Q.pop();
            while(!revQ.empty() && tma[revQ.top().index] != -revQ.top().val)
                revQ.pop();
            if(rest){
                Q.push({x + va[a], a});
                revQ.push({-(x + va[a]), a});
                tma[a] = x + va[a];
                --rest;
            } else if(-revQ.top().val > x + va[a]){
                Q.push({x + va[a], a});
                revQ.pop();
                revQ.push({-(x + va[a]), a});
                tma[a] = x + va[a];
                --idx;
            }
            cnt--;
        }
        //printf("\n");
        ansA = max(ansA, x);
    }
    printf("%d", ansA);

    return 0;
}