| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1234533 | oolimry | Boxes with souvenirs (IOI15_boxes) | C11 | 0 ms | 0 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;
}