#include <bits/stdc++.h>
using namespace std;

struct St {
long long s;
int c;
bool operator<(const St& o) const {
if (s != o.s) return s < o.s;
return c < o.c;
}
};

St mx(St a, St b) {
return a < b ? b : a;
}

St get_mx(const vector<int>& a, long long lam) {
int n = a.size();
St d0 = {0, 0};
St d1 = {-(long long)a[0] - lam, 1};
for (int i = 1; i < n; ++i) {
St n0 = mx(d0, d1);
long long v = -(long long)a[i];
St n1_ext = {d1.s + v, d1.c};
St n1_str = {d0.s + v - lam, d0.c + 1};
St n1 = mx(n1_ext, n1_str);
d0 = n0;
d1 = n1;
}
return mx(d0, d1);
}

long long solve(int n, int k, vector<int>& a) {
long long base = 0;
for (int i = 0; i < n; ++i) {
base += a[i];
}
St r0 = get_mx(a, 0);
long long best = 0;
if (r0.c <= k) {
best = r0.s;
} else {
long long l = 0, r = 2e14;
while (l <= r) {
long long mid = l + (r - l) / 2;
St cur = get_mx(a, mid);
if (cur.c >= k) {
best = cur.s + mid * k;
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return base + 2 * best;
}

INFOSYS ✅

💻 Live Coding Test | Projects | Interviews | OA & Hackathons Help

📢 DM @Codemaster004

🔥  Amazon is Hiring! 🔥

💻 Role:
Software Dev Engineer - 1 (SDE-1) - Bengaluru

🎓 Eligibility:
2024 / 2025 batch
Bachelor’s degree
1+ YOE (Years of Experience)

📌 Key Requirements:
Experience in at least 1 programming language
Job Id: 10432823

👇 Click below to apply:
🔗 Application Link : https://www.amazon.jobs/en/jobs/10432823/software-development-engineer-i-finops-fp-a

🔥 Infosys is Hiring! 🔥

💻 Role:
Digital Specialist Engineer (DSE) & Specialist Programmer (SP)

Location: PAN India

🎓 Eligibility:
2024, 2025 & 2026 Batch
BE / B.Tech, ME / M.Tech, MCA, M.Sc

Experience: Freshers

📌 Key Requirements:
Salary package ranges from ₹6.25 LPA – ₹21 LPA

Apply as soon as possible

👇 Click below to apply:

🔗 Application Link : https://surveys.infosysapps.com/r/a/SPOffCampusregistration_apr26

💻 Live Coding Test | Projects | Interviews | OA & Hackathons Help

📩 DM: @codemaster004

🚨 Electrifex is Hiring! 🚨

💻 Role:
* Software Engineer

🎓 Eligibility:
* Batch : 2020/21/22/23/24/25/26
* Bachelor's degree

📌 Key Requirements:
* Direct Test (No Resume Shortlisting)
* Selection Process: Online Quiz (30 Min), Coding Test, 2 Technical Interviews, and HR Interview
* CTC: ₹6 Lakhs to ₹8 Lakhs per year

👇 Click below to apply:
🔗 Application Link : https://talents.electrifex.com/


💻 Live Coding Test | Projects | Interviews | OA & Hackathons Help

📢 Join our channel: @Codemaster004