Submission #1017165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017165		huutuan	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	548 ms	296616 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

using namespace std;

int dist(int L, int l, int r){
   if (l>r) swap(l, r);
   return min(r-l, L+l-r);
}

int calc(int L, int l, int r){
   return dist(L, 0, l)+r-l+dist(L, 0, r);
}

const int MN=1e7+10;
long long f[MN], g[MN];

long long delivery(int N, int K, int L, int p[]) {
   K=min(K, N);
   deque<int> dq;
   dq.push_back(0);
   g[0]=f[0]+dist(L, 0, p[0])-p[0];
   f[0]=0;
   for (int i=1; i<=N; ++i){
      while (dq.size() && i-dq.front()>K) dq.pop_front();
      f[i]=g[dq.front()]+p[i-1]+dist(L, 0, p[i-1]);
      if (i<N){
         g[i]=f[i]-p[i]+dist(L, 0, p[i]);
         while (dq.size() && g[dq.back()]>=g[i]) dq.pop_back();
         dq.push_back(i);
      }
   }
   return f[N];
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30