usOJ

( ext{Description})

( ext{Goose!}) 有 (n) 个二次函数，每个函数代入 (x_i) 求值。

现在她想知道在 (sum_{i=1}^nx_i=m) 且 (x_i) 为正整数下所有函数值之和的最小值。

保证 (nle m,a_i>0)。

( ext{Solution})

首先这里有一个很重要的条件：(a>0)。

我们可以算出当函数加 (1) 时（为了保证是正整数，初始 (x_i=1)）的变化量是：(2*a*x+a+b)，可以发现，(x) 变大时，这个变化量一定是变大的（还可以用导数来理解，容易发现导数有关 (x) 的项系数是 (2a)）。

那么我们就可以贪心了：先算出每个函数 (x) 为 (1) 的 (sum) 值，每次找出最小的变化量再加上去。

( ext{Code})

#include<cstdio>
#include<cctype>
#include<queue>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

ll n, a[N], b[N], c[N], sum, minn[N];

ll calc(const int x) {
    return minn[x] * a[x] * 2 + a[x] + b[x];
}

struct node {
    int id;
    node() {}
    node(const int Id) {
    	id = Id;
	}
    bool operator < (const node &x) const {
        return calc(id) > calc(x.id);
    }
}tp;
priority_queue <node> q;

ll read() {
    ll x = 0, f = 1;
    char s = getchar();
    while(! isdigit(s)) {
        if(s == '-')
            f = -1;
        s = getchar();
    }
    while(isdigit(s)) {
        x = (x << 1) + (x << 3) + (s ^ 48);
        s = getchar();
    }
    return x * f;
}

ll cal(const int id, const int x) {
    return a[id] * x * x + b[id] * x + c[id];
}

int main() {
    freopen("function.in", "r", stdin);
    freopen("function.out", "w", stdout);
    n = read();
    ll m = read();
    for(int i = 1; i <= n; ++ i) {
        a[i] = read();
        b[i] = read();
        c[i] = read();
        sum += cal(i, 1);
        minn[i] = 1;
        q.push(node(i));
    }
    m -= n;
    while(m --) {
        tp = q.top();
        q.pop();
        sum += calc(tp.id);
        ++ minn[tp.id];
        q.push(tp);
    }
    printf("%lld
", sum);
    return 0;
}