Submission #601672

#TimeUsernameProblemLanguageResultExecution timeMemory
601672MazaalaiMeetings (IOI18_meetings)C++17
19 / 100
526 ms399980 KiB
#include "meetings.h" #include <bits/stdc++.h> #define sz(x) (int)x.size() #define ALL(x) x.begin(), x.end() #define chmax(a, b) a=max(a,b) #define chmin(a, b) a=min(a,b) #define pb push_back #define ff first #define ss second using namespace std; using ll = long long; using VI = vector <int>; using PII = pair <int, int>; int n, m, q; const int N = 5001; ll dp[N][N]; vector<long long> minimum_costs(vector<int> h, vector<int> L, vector<int> R) { n = sz(h); q = sz(L); // cout << n << ' ' << q << '\n'; vector<long long> ans(q, 1e18); for (int i = 0; i < n; i++) { for (int j = i, cur = 0; j < n; j++) { cur = max(cur, h[j]); dp[i][j] = cur; if (j > i) dp[i][j] += dp[i][j-1]; } for (int j = i, cur = 0; j >= 0; j--) { cur = max(cur, h[j]); dp[i][j] = cur; if (j < i) dp[i][j] += dp[i][j+1]; } } for (int i = 0; i < q; i++) { int l = L[i], r = R[i]; ll& res = ans[i]; for (int mid = l; mid <= r; mid++) { chmin(res, dp[mid][l]+dp[mid][r]-h[mid]); } } return ans; }
#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...