Cod sursa(job #931449)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 28 martie 2013 11:26:52
Problema Barbar Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>

using namespace std;

ifstream fin("lumanari.in");
ofstream fout("lumanari.out");

int n, timpref, a[200000];
long long sum, numar;

bool cmp(int a, int b){
    return a > b;
}

void Citire(){
    long long x;

    fin>>n;
    for(int i=1; i<=n;i++){
        fin>>a[i];
        if(a[i] > 0){
            sum += a[i];
            timpref++;
        }
    }
    sort(a+1, a+n+1, cmp);
    n = timpref;
}

int zile(long long timp){
     long long timp2 = timp, neg = 0, contor = 0, i = 1, ultime;
     while(timp2 && i<=n){
            if(a[i] - timp2 < 0) {contor++; neg += (a[i] - timp2);}
            else ultime += a[i];
            timp2--; i++;
     }

     if(ultime > 0 && i<=n) neg += ultime;

     if(neg < 0 && !timp2)
            while(i <= n && neg < 0){
                neg += a[i];
                if(neg < 0) contor++;
                i++;
            }
    if(neg >= 0 && !timp2) return 1;
    return 0;
}

void Nrzile(){
    long long st = -1, dr = timpref, m;
    bool ultim;
    while(dr - st > 1){
        m = dr + (st-dr)/2;
        if(zile(m)) st = m, ultim = 1;
        else dr = m, ultim = 0;
    }
    if(ultim == 1)
    fout<<m;
    else fout<<m-1;
}

int main()
{
    Citire();
    Nrzile();
    return 0;
}