萌新代码求调
  • 板块P2034 选择数字
  • 楼主1nes
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/23 18:07
  • 上次更新2024/5/23 20:28:11
查看原帖
萌新代码求调
1114867
1nes楼主2024/5/23 18:07
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N = 1e5 + 3;
int n , k;
ll a[N] , s[N] , f[N] , ds[N];
deque<ll> q;
ll query(int x){
	ds[x] = f[x - 1] - s[x];
	while(q.size() && ds[q.front()] < ds[x])	q.pop_front();
	while(q.size() && q.back() < x - k)	q.pop_back();
	q.push_front(x);
	return ds[q.back()];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	q.clear();
	for(int i = 1 ; i <= n ; i++)	f[i] = query(i) + s[i];
	cout << f[n];
	return 0;
}
2024/5/23 18:07
加载中...