Submission #590124

#TimeUsernameProblemLanguageResultExecution timeMemory
590124AlperenTBoxes with souvenirs (IOI15_boxes)C++17
100 / 100
720 ms287056 KiB
#include <bits/stdc++.h> #include "boxes.h" using namespace std; const long long INF = 2e18; struct MinQue{ deque<long long> dque; void clear(){ dque.clear(); } void push(long long x){ while(!dque.empty() && dque.back() > x) dque.pop_back(); dque.push_back(x); } void pop(long long x){ assert(!dque.empty()); if(dque.front() == x) dque.pop_front(); } long long getmin(){ assert(!dque.empty()); return dque.front(); } }; long long delivery(int n, int k, int l, int p[]){ long long arr[n + 2] = {}, prefix[n + 2] = {}, suffix[n + 2] = {}; for(int i = 1; i <= n; i++) arr[i] = p[i - 1]; MinQue que; que.push(0); for(int i = 1; i <= n; i++){ if(i - k - 1 >= 0) que.pop(prefix[i - k - 1] + arr[i - k - 1]); prefix[i] = que.getmin() + arr[i]; que.push(prefix[i] + arr[i]); } arr[n + 1] = l; que.clear(); que.push(0); for(int i = n; i >= 1; i--){ if(i + k + 1 <= n + 1) que.pop(suffix[i + k + 1] + (l - arr[i + k + 1])); suffix[i] = que.getmin() + (l - arr[i]); que.push(suffix[i] + (l - arr[i])); } long long ans = INF; for(int i = 0; i <= n; i++){ ans = min(ans, prefix[i] + min(arr[i], l - arr[i]) + suffix[i + 1] + min(arr[i + 1], l - arr[i + 1])); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...