当前位置:网站首页>D - function (HDU - 6546) girls' competition
D - function (HDU - 6546) girls' competition
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
typedef long long ll;
struct node
{
ll a,b,c;
ll mark; // Mark x Increase of one function at a time f(x+1)-f(x);
ll x;
bool operator<(const node &t) const{
return mark > t.mark;
}
};
int main()
{
ll n,m;
while(~scanf("%lld%lld",&n,&m))
{
priority_queue<node> pq;// Custom priority queue ;
ll ans=0;
for(int i=0;i<n;i++){
node t;
scanf("%lld%lld%lld",&t.a,&t.b,&t.c);
ans+=t.a+t.b+t.c; // When x Equal to a moment ;
t.x=1;
t.mark=t.a*(2*t.x+1)+t.b; //f(x+1)-f(x), Growth ;
pq.push(t); // Push the ;
}
for(int i=0;i<m-n;i++){
node temp=pq.top();
// Increase every time 1 Least function , have to x Value , And then again temp.x++;
pq.pop();
temp.x++;
temp.mark=temp.a*(2*temp.x+1)+temp.b;// growth f(x+1)-f(x);
pq.push(temp);
ans+=temp.a*(2*temp.x-1)+temp.b;
//ans yes f(x-1) Value , So subtract the amount of growth ;
}
printf("%lld\n",ans);
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
If you want to apply for a programmer, your resume should be written like this [essence summary]
Record of brushing questions with force deduction -- complete knapsack problem (I)
Information security - threat detection - detailed design of NAT log access threat detection platform
CS zero foundation introductory learning record
Path problem before dynamic planning
Ball Dropping
Opencv learning log 19 skin grinding
1010 things that college students majoring in it must do before graduation
The most complete programming language online API document
【练习-10】 Unread Messages(未读消息)
初入Redis
差分(一维,二维,三维) 蓝桥杯三体攻击
Optimization method of path problem before dynamic planning
编程到底难在哪里?
数据在内存中的存储&载入内存,让程序运行起来
Matlab comprehensive exercise: application in signal and system
Nodejs+vue网上鲜花店销售信息系统express+mysql
Information security - security professional name | CVE | rce | POC | Vul | 0day
区间和------离散化
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool




![[exercise-4] (UVA 11988) broken keyboard = = (linked list)](/img/59/78ca7170ab1fd364ec44cfbcdc7ab5.png)




