Pagini recente » Rating Petrus Andreea Madalina (MadaPetrus) | Cod sursa (job #2024442) | Cod sursa (job #457328) | Cod sursa (job #537979) | Cod sursa (job #931449)
Cod sursa(job #931449)
#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;
}