Submission #123671

#	Time	Username	Problem	Language	Result	Execution time	Memory
123671		dragonslayerit	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	604 ms	293856 KiB

boxes

#include "boxes.h"
#include <algorithm>
#include <cstdio>

long long prefix[10000002];
long long suffix[10000002];

long long delivery(int N, int K, int L, int p[]) {
  for(int i=1;i<=N;i++){
    prefix[i]=((i>=K)?prefix[i-K]:0)+2*p[i-1];
  }
  for(int i=N;i>=1;i--){
    suffix[i]=((i+K<=N+1)?suffix[i+K]:0)+2*(L-p[i-1]);
  }
  long long ans=1e18;
  for(int i=1;i<=N+1;i++){
    ans=std::min(ans,prefix[i-1]+suffix[i]);
  }
  for(int i=1;i+K<=N+1;i++){
    ans=std::min(ans,prefix[i-1]+suffix[i+K]+L);    
  }
  return ans;
}

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