Problem D. maxsum

NC229643. Problem D. maxsum

描述

Give you $n$ numbers $a_i$ , define $S_{(l, r)}=\sum\limits_{i=l}^r a_i (1 \leq l \leq r \leq n)$ , obviously There are $\dfrac{n \times (n+ 1)}{2} S$ ，the person who made the question wants to know the top $w S$ .

输入描述

The first line is two integers 
The number of    in the second line, the number of    is

输出描述

Output the number of , which represents the answer, separated by spaces.

示例1

输入:

6 8
1 1 4 5 1 4

输出:

16 15 14 12 11 11 10 10

示例2

输入:

7 8
1 9 1 9 8 1 0

输出:

29 29 28 28 28 27 20 19

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 93ms, 内存消耗: 11352K, 提交时间: 2022-07-16 13:08:02

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N=2e5+7;

ll n,w,a[N],sum[N];
priority_queue<ll>s;

int main()
{
	cin>>n>>w;
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	
	for(int i=0;i<=1000&&i<=n;i++)
	{
		for (int j=0;j<=1000&&j<=n;j++)
		{
			s.push(sum[n-i]-sum[j]);
		}
	}
	for(int i=0;i<w;i++)
	{
		cout<<s.top()<<" ";
		s.pop();
	}
}

上一题

下一题

详情