제출 #1234534

#제출 시각아이디문제언어결과실행 시간메모리
1234534oolimryBoxes with souvenirs (IOI15_boxes)C++20
100 / 100
1491 ms105136 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define mp make_pair #define pii pair<int,int> #define ff first #define ss second #define pb push_back #define debu(x) cerr<<#x<<" = "<<x<<"\n"; #define debu2(x,y) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<"\n"; //forgetting to make my priority queue a minimum heap one :( int n,k,l; #define int long long int dist(int x, int y) { if(x>y)swap(x,y); return min(y-x,l-y+x); } #undef int long long delivery(int N, int K, int L, int p[]) { #define int long long n=N;k=K;l=L; int ans=0; int prev=0; for(int i=0;i<N;i++) { ans+=dist(prev,p[i]); prev=p[i]; } ans+=dist(prev,0); priority_queue<pii,vector<pii>,greater<pii>>dp; dp.push(mp(0,0)); for(int i=1;i<N;i++) { int curr=dist(0,p[i-1])+dist(0,p[i])-dist(p[i-1],p[i]); while(i-dp.top().ss>K){dp.pop();} dp.push(mp(curr+dp.top().ff,i)); } while(n-dp.top().ss>K){dp.pop();} ans+=dp.top().ff; #undef int 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...