#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> T(N);
for (int i = 0; i < N; ++i) {
cin >> T[i];
}
// DP array to store the minimum waiting time for the first i customers
vector<int> dp(N + 1, LLONG_MAX); // Initialize dp with a large value
dp[0] = 0; // No customers, no waiting time
// We iterate through each customer and calculate the minimum waiting time
for (int i = 1; i <= N; ++i) {
int max_time_in_group = 0;
// Consider all possible groupings that end at customer i
for (int j = i - 1; j >= 0; --j) {
max_time_in_group = max(max_time_in_group, T[j]);
dp[i] = min(dp[i], dp[j] + max_time_in_group * (i - j));
}
}
cout << dp[N] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |