1060번: 구간

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

#include<cstdio>
#include<algorithm>
using namespace std;
int l, n, a[52], cnt;
pair<long long, int> p[51 * 199];
int main() {
    scanf("%d", &l);
    for (int i = 1; i <= l; i++) scanf("%d", a + i);
    scanf("%d", &n);
    sort(a + 1, a + l + 1);
    for (int i = 1; i <= n&&i < a[1]; i++) p[cnt++] = { (long long)i*(a[1] - i) - 1,i };
    for (int i = 1; i < n; i++) p[cnt++] = { (long long)1e15,a[l] + i };
    for (int i = 1; i <= l; i++) {
        p[cnt++] = { 0,a[i] };
        for (int j = 1; j < n; j++) {
            if (i && a[i] - j > a[i - 1]) p[cnt++] = { (long long)j*(a[i] - a[i - 1] - j) - 1,a[i] - j };
            if (i<l&&a[i] + j < a[i + 1]) p[cnt++] = { (long long)j*(a[i + 1] - a[i] - j) - 1,a[i] + j };
        }
    }
    sort(p, p + cnt);
    cnt = unique(p, p + cnt) - p;
    for (int i = 0; i < n; i++) printf("%d ", p[i].second);
    return 0;
}