#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long solve(int n, vector<vector<int>>& g) {
if (n == 0) return 0;
vector<vector<long long>> dp(n, vector<long long>(n, -2e18));
dp[0][0] = g[0][0];

for (int s = 1; s <= 2 * n - 2; ++s) {
vector<vector<long long>> ndp(n, vector<long long>(n, -2e18));
int mn = max(0, s - n + 1);
int mx = min(s, n - 1);

for (int x1 = mn; x1 <= mx; ++x1) {
for (int x2 = mn; x2 <= mx; ++x2) {
int y1 = s - x1;
int y2 = s - x2;
long long prv = -2e18;

if (x1 > 0 && x2 > 0) prv = max(prv, dp[x1 - 1][x2 - 1]);
if (x1 > 0 && y2 > 0) prv = max(prv, dp[x1 - 1][x2]);
if (y1 > 0 && x2 > 0) prv = max(prv, dp[x1][x2 - 1]);
if (y1 > 0 && y2 > 0) prv = max(prv, dp[x1][x2]);

if (prv != -2e18) {
long long val = g[x1][y1];
if (x1 != x2) val += g[x2][y2];
ndp[x1][x2] = prv + val;
}
}
}
dp = ndp;
}
return dp[n - 1][n - 1];
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int n;
if (cin >> n) {
vector<vector<int>> g(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}

auto result = solve(n, g);
cout << result << "\n";
}
return 0;
}

Infosys ✅

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

📢 DM @Codemaster004

#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