Submission #823336

#TimeUsernameProblemLanguageResultExecution timeMemory
823336Dremix10Meetings (IOI18_meetings)C++17
19 / 100
2976 ms786432 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define F first #define S second #define all(x) (x).begin(),(x).end() typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; const int N = 3e5+5; const ll INF = 1e18+5; const int MOD = 1e9+7; vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) { int n = arr.size(); int q = L.size(); int i,j,k; vector<ll> ans(q); ll dp[n][n]; for(i=0;i<n;i++){ // good i is always local minima //if(i-1 >= x && arr[i-1] < arr[i] || i+1 <= y && arr[i+1] < arr[i])continue; ll curr = 0; int maxi = 0; for(j=i;j<n;j++){ maxi = max(maxi,arr[j]); curr += maxi; dp[i][j] = curr; } maxi = 0; curr = 0; for(j=i;j>=0;j--){ maxi = max(maxi,arr[j]); curr += maxi; dp[i][j] = curr; } } for(k=0;k<q;k++){ int x = L[k]; int y = R[k]; ll res = INF; for(i=x;i<=y;i++){ res = min(res,dp[i][x] + dp[i][y] - arr[i]); } ans[k] = res; } 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...