Codeforces Round #178 (Div. 2)
Shaass has decided to hunt some birds. There are
Sometimes Shaass shots one of the birds and the bird dies (suppose that this bird sat at the
Shaass puts the books on the bookshelf in the following way. First he selects some of the books and put them vertically. Then he puts the rest of the books horizontally above the vertical books. The sum of the widths of the horizontal books must be no more than the total thickness of the vertical books. A sample arrangement of the books is depicted in the figure.
Help Shaass to find the minimum total thickness of the vertical books that we can achieve.
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int f[210];int main(){ int n, t[111], w[111], W = 0; cin >> n; for (int i = 0; i < n; i++) cin >> t[i] >> w[i], W += w[i]; for (int j = 1; j <= 200; j++) f[j] = - 1000000; for (int i = 0; i < n; i++) for (int j = 200; j >= 0; j--) if (j >= t[i]) { f[j] = max(f[j], f[j - t[i]] + w[i]); } for (int i = 0; i <= 200; i++) if (i >= W - f[i]) { cout << i << endl; return 0; }}