제출 #392672

#제출 시각아이디문제언어결과실행 시간메모리
392672JimmyZJX모임들 (IOI18_meetings)C++14
0 / 100
349 ms399784 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) LL dp[5003][5003]; int maxI[5003]; VL minimum_costs(Vi H, Vi L, Vi R) { int n = H.size(), q = L.size(); memset(dp, 0, sizeof(dp)); forR(i, n) { dp[i][i] = H[i]; maxI[i] = i; } for (int d = 1; d < n; d++) { for (int i = 0; i + d < n; i++) { int j = i + d; if (H[j] > H[maxI[i]]) maxI[i] = j; int mi = maxI[i]; if (mi == i) { dp[i][j] = H[i] + dp[i + 1][j]; } else if (mi == j) { dp[i][j] = H[j] + dp[i][j - 1]; } else { int hMax = H[mi]; dp[i][j] = min(dp[i][mi - 1] + hMax * (j - mi + 1), dp[mi + 1][j] + hMax * (mi - i + 1)); } } } VL ans; forR(i, q) { ans.push_back(dp[L[i]][R[i]]); } return ans; } #ifdef TEST_LOCAL int main() { minimum_costs(Vi{ 2,4,3,5 }, Vi{ 0, 1 }, Vi{ 2, 3 }); return 0; } #endif
#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...