Gym - 101810A ACM International Collegiate Programming Contest (2018)
2024-09-07 11:16:16
bryce1010模板
http://codeforces.com/gym/101810/problem/A
大模拟，写崩了，代码借队友的。。。。。。
注意处理段与段的连接问题：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
long long l,r,val;
node(){}
node(long long ll,long long rr,long long vval)
{
l=ll;
r=rr;
val=vval;
}
}ar[maxn];
bool cmp(node a,node b)
{
return a.l<b.l;
}
int main(){
int t,m;
long long k;
scanf("%d",&t);
while(t--)
{
scanf("%d%lld",&m,&k);
int u,v,cost;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&cost);
ar[i]=node(u,v,cost);
}
sort(ar,ar+m,cmp);
long long sum=0,ans=0;
int pre=0;
for(int i=0;i<m;)
{
if(ar[i].r-ar[pre].l+1<=k)
{
sum+=(ar[i].r-ar[i].l+1)*ar[i].val;
ans=max(ans,sum);
i++;
}
else
{
if(ar[i].l-ar[pre].l>=k)
{
if(ar[i].r-ar[pre].r<=k)
{
ans=max(ans,sum+(ar[i].r-ar[i].l+1)*ar[i].val-(ar[i].r-ar[pre].l+1-k)*ar[pre].val);
sum+=(ar[i].r-ar[i].l+1)*ar[i].val;
i++;
}
else
{
sum-=(ar[pre].r-ar[pre].l+1)*ar[pre].val;
pre++;
}
}
else
{
ans=max(ans,sum+(k-ar[i].l+ar[pre].l)*ar[i].val);
if(ar[i].r-ar[pre].r<k)
{
sum+=(ar[i].r-ar[i].l+1)*ar[i].val;
ans=max(ans,sum-(ar[i].r-ar[pre].l+1-k)*ar[pre].val);
i++;
}
else
{
sum-=(ar[pre].r-ar[pre].l+1)*ar[pre].val;
pre++;
}
}
}
}
printf("%lld\n",ans);
}
return 0;
}
最新文章
- 支持“ApplicationDbContext”上下文的模型已在数据库创建后发生更改
- Objective-C：Foundation框架-常用类-NSDictionary
- css3 过渡记
- 1.2机器学习基础下--python深度机器学习
- 第二节 EAN 8 码 / EAN 13 码
- vi 使用教程
- redis可视化工具redisClient
- 论MyBatis日志
- HTTP协议与TCP/IP协议
- Helicute FPV App Privacy Policy
- log4net可视化查询
- 68.jq---tab选项实现网页定点切换
- day14 十四、三元运算符，推导式，匿名内置函数
- zombodb 数据类型映射
- Kotlin入门(3)基本变量类型的用法
- 【CSS】元素样式
- 第五个神奇的电梯（代码抢先看<1>）
- C++第六次作业
- System 类的使用
- 【转载】Java 9 新特性——模块化