Submission #169886

#	Time	Username	Problem	Language	Result	Execution time	Memory
169886		AlexLuchianov	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	604 ms	294136 KiB

boxes

#include "boxes.h"
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 10000000;
ll const inf = 1000000000000000000LL;

ll pref[1 + nmax], suff[1 + nmax];

long long delivery(int N, int K, int L, int p[]) {
  for(int i = 0; i < N; i++)
    if(i < K)
      pref[i] = MIN(2 * p[i], L);
    else
      pref[i] = pref[i - K] + MIN(2 * p[i], L);
  for(int i = N - 1; 0 <= i; i--)
    if(i + K < N)
      suff[i] = suff[i + K] + MIN(2 * (L - p[i]), L);
    else
      suff[i] = MIN(2 * (L - p[i]), L);

  ll result = inf;


  for(int i = 0; i <= N; i++) {
    ll cost = 0;
    if(0 < i) {
      cost += pref[i - 1];
    }
    if(i < N)
      cost += suff[i];

    if(cost < result)
      result = cost;
  }
  return result;
}

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