u1ik on 06/26/08

# Dwarves solution

/ Published in: C++

Probably not correct, but passed tests http://www.liis.ro/~lotinfo2008/probleme/pitici.zip

`#include <cstdio>#include <algorithm>using namespace std; struct Dwarf{    int l, h;    bool sacrificed;    bool operator < (const Dwarf& d) const    {        return l + h > d.l + d.h;    }}; const int N = 2000;Dwarf d[N];int n;int H; int main(){    scanf("%d", &n);    for (int i = 0; i < n; ++i)    {        scanf("%d %d", &d[i].h, &d[i].l);        d[i].sacrificed = false;    }    scanf("%d", &H);    sort(d, d + n);    int h_s = 0;    for (int i = n-1; i >= 0; --i)    {        int h_p = 0;        for (int j = 0; j < i; ++j) h_p += d[j].h;        if (d[i].h + d[i].l + h_s + h_p < H)        {            int k = i;            for (int j = i + 1; j < n; ++j)            if (!d[j].sacrificed)            {                if (d[j].h > d[k].h) k = j;            }            d[k].sacrificed = true;            h_s += d[k].h;        }    }       int res = 0;    for (int i = 0; i < n; ++i)        if (d[i].sacrificed) res++;    printf("%d\n", n - res);    return 0;}`