2019年ccpc女子大会再現試合問題解C

2019年ccpc女子大会再現試合問題解C
タイトル:Function Time Limit:2000/1000 MS(Java/others)Memory Limit:524288/5224288 K(Java/others)Total Submission(s):0 Accepted Submission(s):0
Problem Description wlsには、n個の二次関数Fi(x)=aix 2+bix+ci(1≦i≦n)がある.現在、Σni=1 xi=mでxが正の整数である条件下でΣni=1 Fi(xi)の最小値を求めている.この最小値を要求します.
Inputの最初の行の2つの正の整数n,m.次のn行は、各行の3つの整数a,b,cがそれぞれ二次関数の二次項、一次項、定数項係数を表す.1 ≤ n ≤ m ≤ 100, 000 1 ≤ a ≤ 1, 000 −1, 000 ≤ b, c ≤ 1, 000
Outputは1行1つの整数で答えを表します.
Sample Input
2 3 1 1 1 2 2 2
Sample Output
13
考え方、mはまず各関数式に少なくとも1つの1を分けて和を求め、それからmの残りの数字に対して、1を加えて増加できる数字を求めて優先キューメンテナンスを利用して1を加えた後に最も増加する関数に1を加えて、最後に結果を出して、先輩aのこの問題orz、tql.
ACコード:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define fi first
#define se second
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define root 1,n,1
#define PB push_back
#define MP make_pair
#define pi 3.1415926535898
#define MS(x,y) memset(x,y,sizeof(x))
#define lowbit(a)  (a&(-a))

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL,LL> P;
const int maxn = 1e5 + 10,modd = 1e9 + 7,inf = 0x3f3f3f3f,INF = 0x7fffffff,hmod1=0x48E2DCE7,hmod2=0x60000005;
const int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
const double eps = 1e-8;

template <class T> inline void scand(T &x){char c;x=0;while((c=getchar())<'0');while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();}
inline LL min(LL a,LL b){return a < b ? a : b;}
inline LL max(LL a,LL b){return a > b ? a : b;}
inline LL gcd(LL a,LL b){ return b==0? a: gcd(b,a%b); }
inline LL exgcd(LL a,LL b,LL &x,LL &y){ LL d; (b==0? (x=1,y=0,d=a): (d=exgcd(b,a%b,y,x),y-=a/b*x)); return d; }
inline LL qpow(LL a,LL n){LL sum=1;while(n){if(n&1)sum=sum*a%modd;a=a*a%modd;n>>=1;}return sum;}
inline LL qmul(LL a,LL n){LL sum=0;while(n){if(n&1)sum=(sum+a)%modd;a=(a+a)%modd;n>>=1;}return sum;}
inline LL inv(LL a) {return qpow(a,modd-2);}
inline LL madd(LL a,LL b){return (a%modd+b%modd)%modd;}
inline LL mmul(LL a,LL b){return a%modd * b%modd;}
inline void uadd(LL &a,LL b){a = madd(a,b);}
inline void umul(LL &a,LL b){a = mmul(a,b);}

struct Node
{
  LL id,x,val;
  bool operator < (const Node &a) const{
    return val > a.val;
  }
};

LL n,m,summ,sumc,a[maxn],b[maxn],c[maxn];
priority_queue<Node> pq;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  cin >> n >> m;
  for(int i=1;i<=n;i++)
  {
    cin >> a[i] >> b[i] >> c[i];
    summ += (a[i] + b[i] + c[i]);
    pq.push(Node{i,2,3*a[i]+b[i]});
  }
  for(int i=0;i<m-n;i++)
  {
    Node f = pq.top();pq.pop();
    summ += f.val;
    pq.push(Node{f.id,f.x+1,a[f.id]*(f.x+1)*(f.x+1)+b[f.id]*(f.x+1)-a[f.id]*(f.x)*(f.x)-b[f.id]*f.x});
  }
  cout << summ << endl;
}