제출 #396963

#제출 시각아이디문제언어결과실행 시간메모리
396963Andyvanh1선물상자 (IOI15_boxes)C++14
70 / 100
2064 ms464652 KiB
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <stack> #include <queue> #include <map> #include <math.h> using namespace std; #define pb push_back #define INF INT32_MAX #define vt vector typedef vt<int> vi; typedef pair<int,int> pii; typedef tuple<int,int,int> tiii; typedef long long ll; #define MOD 1000000007 ll delivery(int n, int k, int l, int arr[]){ if(k==1){ ll ans = 0; for(int i = 0; i < n; i++){ ans+=2*min(arr[i],l-arr[i]); } return ans; }else if(k==n){ if(arr[n-1]<=l/2){ return arr[n-1]*2; }else if(arr[0]>l/2){ return 2* (l-arr[0]); }else{ int Max1 = 0; int Max2 = 0; int i = 0; for(; i < n; i++){ if(arr[i]<=l/2){ Max1 = max(Max1, arr[i]); }else{ break; } } Max2 = arr[i]; return min(l,2*(Max1+l-Max2)); } }else{ vt<ll> vals1(n+1); vt<ll> vals2(n+1); vt<ll> dp(n+1); dp[0] = 0; multiset<ll> pq1; pq1.insert(dp[0]-2*arr[0]); vals1[0]=dp[0]-2*arr[0]; multiset<ll> pq2; pq2.insert(0); vals2[0] = 0; for(int i = 1; i <= n; i++){ dp[i] = *(pq1.begin())+2*l; dp[i] = min(dp[i],min(*(pq2.begin())+2*arr[i-1],*(pq2.begin())+l)); if(i!=n) { vals1[i] = dp[i] - 2 * arr[i]; vals2[i] = dp[i]; pq1.insert(vals1[i]); pq2.insert(vals2[i]); } if(i-k>=0){ pq1.erase(pq1.find(vals1[i-k])); pq2.erase(pq2.find(vals2[i-k])); } } return dp[n]; } }
#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...