Cod sursa(job #586256)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 30 aprilie 2011 14:17:37
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.35 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N_MAX 50010
int TA[3*N_MAX], TB[3*N_MAX], *t;
int v[2*N_MAX];
int A[N_MAX], B[N_MAX];
int n, na, nb;
int a, b, val;
int sol1, sol2;
void update(int p, int q, int i) {
    if(a <= p && q <= b) {
        t[i] += val;
        return ;
    }
    int m = (p+q)/2;
    if(a <= m) update(p, m, 2*i);
    if(b > m) update(m+1, q, 2*i+1);
    t[i] = min(t[2*i], t[2*i+1]);
}
void query(int p, int q, int i) {
    if(p == q) {
        if(TA[i] > sol1) sol1 = TA[i];
        v[++v[0]] = TA[i];
        TA[i] += A[p];
        return ;
    }
    int m = (p+q)/2;
    if(TA[2*i] < TA[2*i+1]) query(p, m, 2*i);
    else query(m+1,q, 2*i+1);
    TA[i] = min(TA[2*i], TA[2*i+1]);
}
int main() {
    freopen("fabrica.in", "r", stdin);
    freopen("fabrica.out", "w", stdout);
    scanf("%d%d%d", &n, &na, &nb);
    for(int i = 1; i <= na; ++i)
        scanf("%d", &A[i]);
    for(int i = 1; i <= nb; ++i)
        scanf("%d", &B[i]);
    sort(A + 1, A + na + 1);
    sort(B + 1, B + nb + 1);
    na = min(n, na);
    nb = min(n, nb);
    for(int i = 1; i <= na; ++i) {
        a = i; b = i; val = A[i];
        t = TA;
        update(1, na, 1);
    }
    for(int i = 1; i <= n; ++i)
        query(1, na, 1);
    int sol = 0;
    for(int i = 1; i <= n; ++i)
        if(sol < v[i]) sol = v[i];
    printf("%d\n", sol);
    return 0;
}