#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
void ComputeDistanceMatrix(int N, const std::vector<int>& H, std::vector<std::vector<int>>& D)
{
for (int i = 0; i < N; ++i)
{
D[i][i] = H[i];
for (int j = i+1; j < N; ++j)
{
D[i][j] = max(H[j], D[i][j-1]);
}
}
}
long long minCostForCandidateIdx (const std::vector<int>& H, int L, int R, int candidateIdx,
const std::vector<std::vector<int>>& D)
{
long long costForCandidate = 0;
for (int i = L; i < candidateIdx; ++i)
{
costForCandidate += D[i][candidateIdx];
}
for (int i = candidateIdx; i <= R; ++i)
{
costForCandidate += D[candidateIdx][i];
}
return costForCandidate;
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int Q = L.size();
std::vector<long long> C(Q);
int N = H.size();
std::vector<std::vector<int>> distanceMatrix(N, std::vector<int>(N));
ComputeDistanceMatrix(N, H, distanceMatrix);
for (int j = 0; j < Q; ++j) {
long long minSize = LLONG_MAX;
for (int candidateIdx = L[j]; candidateIdx <= R[j]; ++candidateIdx)
{
long long curCost = minCostForCandidateIdx(H, L[j], R[j], candidateIdx, distanceMatrix);
minSize = min(minSize, curCost);
}
C[j] = minSize;
}
return C;
}
