Submission #979609

#	Time	Username	Problem	Language	Result	Execution time	Memory
979609		kilkuwu	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	379 ms	215868 KiB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

#ifdef LOCAL
#include "template/debug.hpp"
#else 
#define dbg(...) ;
#define timer(...) ;
#endif

long long delivery(int N, int K, int L, int p[]) {
  int split = std::upper_bound(p, p + N, L / 2) - p;


  std::vector<long long> dp(N);

  for (int i = N - 1; i >= split; i--) {
    if (i + K < N) {
      dp[i] = dp[i + K] + (L - p[i]) * 2;
    } else {
      dp[i] = (L - p[i]) * 2;
    }
  }

  for (int i = 0; i < split; i++) {
    if (i - K >= 0) {
      dp[i] = dp[i - K] + p[i] * 2;
    } else {
      dp[i] = p[i] * 2;
    }
  }



  long long ans = split > 0 ? dp[split - 1] : 0;
  ans += (split < N) ? dp[split] : 0;
  long long round = 1e18;
  for (int i = split; i < N && i - K + 1 < split; i++) {
    long long cand = L; // go the entire thing
    cand += i + 1 < N ? dp[i + 1] : 0;
    cand += i - K >= 0 ? dp[i - K] : 0;
    round = std::min(round, cand);
  }

  return std::min(ans, round);
}

#ifdef LOCAL

int main() {

  int N, K, L, i;
  std::cin >> N >> K >> L;

  int *p = (int*)malloc(sizeof(int) * (unsigned int)N);

  for (i = 0; i < N; i++) {
    std::cin >> p[i];
  }

  std::cout << delivery(N, K, L, p) << "\n";
  return 0;
}
#endif

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:13:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   13 |   int split = std::upper_bound(p, p + N, L / 2) - p;
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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