2017 Netease Dual Core

2017.netease.dual.core.cpp

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
using namespace std;

#define ff(i, n) for (int i = 0, END = (n); i < END; i ++)
#define fff(i, n, m) for (int i = (n), END = (m); i <= END; i ++)
#define dff(i, n, m) for (int i = (n), END = (m); i >= END; i --)
#define travel(e, first) for (int e = first, v = vv[first]; ~e; e = nxt[e], v = vv[e])
#define clr(a, b) memset(a, b, sizeof(a))
typedef long long ll;

int n, V;
int goods[55], dp[5000 * 25];

void zero_one_pack(int m) {
    dff (i, V, m) {
        dp[i] += dp[i - m];
    }
}

int main() {
    while (scanf("%d", &n) == 1) {
        int sum = 0;
        ff (i, n) {
            int v; scanf("%d", &v); v /= 1024;
            sum += v; goods[i] = v;
        }
        V = sum / 2;

        clr(dp, 0); dp[0] = 1;

        ff (i, n) {
            zero_one_pack(goods[i]);
        }

        dff (i, V, 0) if (dp[i]) {
            int need = sum - i;
            printf("%d\n", need * 1024);
            break;
        }
    }
}