Submission #1027446

#TimeUsernameProblemLanguageResultExecution timeMemory
1027446KhoaDuyReal Mountains (CCO23_day1problem2)C++14
0 / 25
0 ms348 KiB
#include <iostream> #include <vector> #include <climits> int main() { int N; std::cin >> N; std::vector<int> h(N+1); // 1-indexed array to store heights for(int i = 1; i <= N; i++) { std::cin >> h[i]; } std::vector<std::vector<int>> dp(N+1, std::vector<int>(N+1, INT_MAX)); std::vector<int> sum(N+1, 0); // prefix sum of heights for(int j = 1; j <= N; j++) { sum[j] = sum[j-1] + h[j]; } for(int j = 1; j <= N; j++) { dp[j][j] = 0; // Cost to create a single peak at column j with the last peak at column j is zero for(int i = 1; i < j; i++) { int cost = (h[i] <= h[j] && h[j] <= h[i+1]) ? (sum[j-1] - sum[i]) : INT_MAX; if(cost != INT_MAX) { dp[j][j] = std::min(dp[j][j], dp[i][j-1] + cost); } } } int minCost = INT_MAX; for(int j = 1; j <= N; j++) { minCost = std::min(minCost, dp[N][j]); } std::cout << minCost << std::endl; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...