oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

minimumswap Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

minimumswap.html

Problem Description

Damian has an array A of N numbers, and wants to find the minimum contiguous sum that can be formed.

However, he decides that this is too trivial. Thus, he decides to swap up to K pairs of numbers first, in the hope of making the sum even smaller.

What is the new minimum sum possible?

Input

The first line contains two integers, N and K, the number of integers and the maximum number of swaps possible.

The second line contains N space-separated integers, representing the numbers of the array.

Output

The output should contain one line containing one integer, the minimum contiguous sum that can be formed.

Limits

For all subtasks, |Ai| ≤ 106; 1 ≤ N ≤ 100.

Subtask 1 (19%): K = 0.

Subtask 2 (27%): K = 1.

Subtask 3 (54%): 0 ≤ K ≤ 100.

Subtask 4 (0%): Sample Testcases.

Sample Testcase 1

Input

8 1
-1 5 -5 -3 2 -5 -4 0

Output

-18

Sample Testcase 1 Explanation

Damian swaps the number at position 0 with the number at position 4.

The minimum contiguous sum can then be formed in this way: 2 5 (-5 -3 -1 -5 -4 0)

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
119101s256MBMinimum
227101s256MBMinimum
354311s256MBMinimum
4011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o minimumswap -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.