Cod sursa(job #1815734)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 25 noiembrie 2016 18:29:25
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int v[90005];
long long sp[90005];

int bs(int st, int dr, int val) {
    int mij, last = 0;
    while(st <= dr) {
        mij = (st + dr) / 2;
        if(v[mij] <= val) {
            last = mij;
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }
    return last;
}

int main() {
    freopen("inundatie.in", "r", stdin);
    freopen("inundatie.out", "w", stdout);

    int n, m, t, q, cautare;
    long long rasp;

    scanf("%d%d", &n, &m);
    n = n * m;

    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &v[i]);
    }

    sort(v + 1, v + n + 1);

    for(int i = 1; i <= n; ++ i) {
        sp[i] = sp[i - 1] + v[i];
    }

    scanf("%d", &t);

    for( ; t; -- t) {
        scanf("%d", &q);
        -- q;
        cautare = bs(1, n, q);

        rasp = sp[cautare] + (long long)(n - cautare) * q;

        printf("%lld\n", rasp);
    }

    return 0;
}