Gym 100342E Minima (暴力,单调队列)
2024-08-30 11:47:00
3e7暴力,800ms+过,单调队列维护区间最小值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e7+; int x[maxn], dq[maxn], pos[maxn]; int main()
{
freopen("minima.in","r",stdin);
freopen("minima.out","w",stdout);
int n,m,k; cin>>n>>m>>k;
ll a,b,c; cin>>a>>b>>c;
for(int i = ; i <= k; i++) scanf("%d",x+i);
for(int i = k+; i <= n; i++){
ll t = a*x[i-]+b*x[i-]+c;
x[i] = t;
}
int l = ,r = ;
ll ans = ;
for(int i = ; i <= n; i++){
while(r>l && dq[r-]>=x[i]) r--;
dq[r] = x[i];
pos[r++] = i;
if(i-pos[l] >= m) l++;
if(i>=m) ans+= dq[l];
}
printf("%I64d\n",ans);
return ;
}
最新文章
- [LeetCode] Kth Largest Element in an Array 数组中第k大的数字
- 20155324王鸣宇对C语言课程回顾及对Java的展望
- Android Studio 导入百度地图jar和so的正确方式
- cvsnt 设置用户、修改密码
- Ognl表达式语言
- Android至ViewPager添加切换动画——使用属性动画
- EF LINQ根据某个字段去除重复行
- &; 与 kill -3
- Spring系列(七) Spring MVC 异常处理
- C++系列总结——new和delete
- C#数组,ArrayList,List
- Using a ScrollView - RN4
- python 去除字符串末尾的子串
- 关于vue,webpack 中 “exports is not defined”报错
- numpy库的常用方法
- eclipse中git的author和commiter的修改
- BZOJ2217 [Poi2011]Lollipop 【贪心】
- ORM sqlachemy
- 【转】Oracle 查询库中所有表名、字段名、表名说明、字段名说明
- Javascript间歇调用和超时调用
热门文章
- Asset Catalog Help (八)---Customizing Image Sets for Devices
- Flutter实战视频-移动电商-17.首页_楼层组件的编写技巧
- UVaLive 3905 Meteor (扫描线)
- vr的延迟和渲染效率优化与Nvidia VRWorks
- 51Nod 1099 任务执行顺序 (贪心)
- Devc++贪吃蛇
- [ZPG TEST 114] 括号匹配【树分治 点分治 括号序列】
- CF #541div2 E
- Gym - 101810H ACM International Collegiate Programming Contest (2018)
- 2017";百度之星";程序设计大赛 - 资格赛 度度熊的王国战略