13575번: 보석 가게

https://www.acmicpc.net/problem/13575


FFT 아닌 풀이

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int> > v = { { 0,-1 },{ 1,1 } };
int n, k, a[1000];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0; i < k; i++) {
        vector<pair<int, int> > t;
        for (int j = 0; j < n; j++)
            for (auto it : v) t.push_back({ it.first + a[j],it.second });
        sort(t.begin(), t.end());
        v.clear();
        int s = t[0].second;
        v.push_back(t[0]);
        for (int j = 1; j < t.size(); j++) {
            s += t[j].second;
            if (!s) {
                v.push_back(t[j]);
                if (j != t.size() - 1) v.push_back(t[j + 1]);
            }
        }
    }
    for (int i = 0; i < v.size(); i += 2)
        for (int j = v[i].first; j < v[i + 1].first; j++) printf("%d ", j);
    return 0;
}