Submission #123670

#	Time	Username	Problem	Language	Result	Execution time	Memory
123670		dragonslayerit	Boxes with souvenirs (IOI15_boxes)	C++14	70 / 100	852 ms	432748 KiB

boxes

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

long long prefix[10000000];
long long suffix[10000000];

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: 0 / 30