Ideone.com

fork download

copy

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int SIZE = 1 << 17;
int a[SIZE], b[SIZE], c[SIZE];
long long f(int subscript, long long x) {
    return a[subscript] * x * x + b[subscript] * x + c[subscript];
}
int v[SIZE];
void solve() {
    int n, K;
    cin >> n >> K;
    long long an = 0;
    priority_queue<pair<long long, int>> pq;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        an += f(i, 0);
        v[i] = 0;
        pq.push({f(i, 0) - f(i, 1), i});
    }
    cout << an << endl; 
    while(K--) {
        long long inc = pq.top().first;
        int id = pq.top().second;
        pq.pop();
        an -= inc;
        cout << an << endl; 
        v[id]++;
        pq.push({f(id, v[id]) - f(id, v[id] + 1), id});
    }
    cout << an << '\n';
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Success #stdin #stdout 0.02s 5260KB

stdin

copy

1 5000
1 -10000 -10000

stdout

copy

https://ideone.com/IsJTxx

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language