CF332B.Maximum Absurdity
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Reforms continue entering Berland. For example, during yesterday sitting the Berland Parliament approved as much as n laws (each law has been assigned a unique number from 1 to n). Today all these laws were put on the table of the President of Berland, G.W. Boosch, to be signed.
This time mr. Boosch plans to sign 2_k_ laws. He decided to choose exactly two non-intersecting segments of integers from 1 to n of length k and sign all laws, whose numbers fall into these segments. More formally, mr. Boosch is going to choose two integers a, b (1 ≤ a ≤ b ≤ n - k + 1, b - a ≥ k) and sign all laws with numbers lying in the segments [a; a + k - 1] and [b; b + k - 1] (borders are included).
As mr. Boosch chooses the laws to sign, he of course considers the public opinion. Allberland Public Opinion Study Centre (APOSC) conducted opinion polls among the citizens, processed the results into a report and gave it to the president. The report contains the absurdity value for each law, in the public opinion. As mr. Boosch is a real patriot, he is keen on signing the laws with the maximum total absurdity. Help him.
改革仍在继续进入伯兰德。例如,在昨天的议会会议上,伯兰德议会一次性通过了多达 n 项法律(每项法律被赋予一个从 1 到 n 的唯一编号)。今天,所有这些法律都被呈递到伯兰德总统 G.W. 布施先生的案头,等待签署。
本次,布施先生计划签署 2k 项法律。他决定从 1 到 n 中精确选取两个互不相交、长度均为 k 的整数区间,并签署所有编号落在这些区间内的法律。更准确地说,布施先生将选择两个整数 a、b(满足 1 ≤ a ≤ b ≤ n − k + 1 且 b − a ≥ k),并签署所有编号位于区间 [a;a + k − 1] 和 [b;b + k − 1](含端点)内的法律。
当布施先生选定待签署的法律时,他自然会考虑公众舆论。全伯兰德公共舆论研究中心(APOSC)已就公民意见展开民意调查,并将结果整理成报告提交给总统。该报告中包含了每一项法律在公众舆论中的“荒谬度”值。由于布施先生是一位真正的爱国者,他热切希望所签署法律的总荒谬度尽可能大。请帮助他实现这一目标。
输入格式
The first line contains two integers n and k (2 ≤ n ≤ 2·105, 0 < 2_k_ ≤ n) — the number of laws accepted by the parliament and the length of one segment in the law list, correspondingly. The next line contains n integers _x_1, _x_2, ..., x__n — the absurdity of each law (1 ≤ x__i ≤ 109).
第一行包含两个整数 n 和 k(2≤n≤2⋅105,0<2k≤n)—— 分别表示议会通过的法律数量以及法律列表中每个分段的长度。
下一行包含 n 个整数 x1, x2, …, xn —— 每条法律的荒谬度(1≤xi≤109)。
输出格式
Print two integers a, b — the beginning of segments that mr. Boosch should choose. That means that the president signs laws with numbers from segments [a; a + k - 1] and [b; b + k - 1]. If there are multiple solutions, print the one with the minimum number a. If there still are multiple solutions, print the one with the minimum b.
输出两个整数 a、b —— 表示 Boosch 先生应选择的两个区间的起始位置。这意味着总统将签署编号属于区间 [a; a+k−1] 和 [b; b+k−1] 的法律。若存在多组解,输出其中 a 最小的一组;若仍存在多组解,则输出其中 b 最小的一组。
输入输出样例
输入#1
5 2 3 6 1 1 6
输出#1
1 4
输入#2
6 2 1 1 1 1 1 1
输出#2
1 3
说明/提示
In the first sample mr. Boosch signs laws with numbers from segments [1;2] and [4;5]. The total absurdity of the signed laws equals 3 + 6 + 1 + 6 = 16.
In the second sample mr. Boosch signs laws with numbers from segments [1;2] and [3;4]. The total absurdity of the signed laws equals 1 + 1 + 1 + 1 = 4.
在第一个样例中,布施先生签署了编号属于区间 [1;2] 和 [4;5] 的法律。所签署法律的总荒谬度为 3 + 6 + 1 + 6 = 16。
在第二个样例中,布施先生签署了编号属于区间 [1;2] 和 [3;4] 的法律。所签署法律的总荒谬度为 1 + 1 + 1 + 1 = 4。
输入解题思路,AI测评打分。不知道怎么写?