Submission #1169302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169302		LucaLucaM	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	0 ms	328 KiB

boxes

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

#define debug(x) #x << " = " << x << '\n'

long long delivery(int n, int k, int L, int p[]) {
  std::vector<std::pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    v[i].first = std::min(p[i], L - p[i]);
    v[i].second = p[i];
  } 

  std::sort(v.begin(), v.end());
  std::reverse(v.begin(), v.end());

  long long answer = 0;

  std::vector<int> st, dr;
  for (int i = 0; i < n; i++) {
    if (v[i].first == v[i].second) {
      st.push_back(v[i].first);
    } else {
      dr.push_back(v[i].first);
    }
  }

  std::sort(st.begin(), st.end());
  std::sort(dr.begin(), dr.end());

  while (!st.empty() && !dr.empty() && 2 * (st.back() +  dr.back()) >= L) {
    answer += L;
    for (int i = 0; i < std::min(n, k); i++){ 
      if (v.back().first == v.back().second) {
        st.pop_back();
      } else {
        dr.pop_back();
      }
      v.pop_back();
    }
    n = std::max(0, n - k);
  }

  while (!st.empty()) {
    answer += 2 * st.back();
    for (int i = 0; i < k && !st.empty(); i++) {
      st.pop_back();
    }
  }

  while (!dr.empty()) {
    answer += 2 * dr.back();
    for (int i = 0; i < k && !dr.empty(); i++) {
      dr.pop_back();
    }
  }

  return answer;
}

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