Submission #1181909

#TimeUsernameProblemLanguageResultExecution timeMemory
1181909mehmetkaganDischarging (NOI20_discharging)C++20
0 / 100
1097 ms15940 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...