# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1172749 | anmattroi | Meetings (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
int N = H.size(), Q = L.size();
vector<vector<int64_t> > ansL(N, vector<int64_t>(N, 0)),
ansR(N, vector<int64_t>(N, 0));
for (int i = 0; i < N; i++) {
ansL[i][i] = H[i]; int mx = H[i];
for (int j = i-1; j >= 0; j--) {
mx = max(mx, H[j]);
ansL[i][j] = ansL[i][j+1] + mx;
}
}
for (int i = N-1; i >= 0; i--) {
ansR[i][i] = H[i]; int mx = H[i];
for (int j = i+1; j < N; j++) {
mx = max(mx, H[j]);
ansR[i][j] = ansR[i][j-1] + mx;
}
}
vector<int64_t> ans;
for (int i = 0; i < Q; i++) {
int l = L[i], r = R[i];
int64_t ds = LLONG_MAX;
for (int j = l; j <= r; j++) ds = min(ds, ansL[j][l] + ansR[j][r] - H[j]);
ans.emplace_back(ds);
}
return ans;
}