Submission #1032215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032215		SonicML	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	709 ms	333040 KiB

boxes

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int const NMAX = 1e7;
int arr[1 + NMAX];
ll preC[1 + NMAX];
ll sufC[1 + NMAX];

void buildPreSufC(int n, int k, int l) {
  for(int i = 1;i <= n;i++) {
    if(i <= k) {
      preC[i] = 2 * arr[i];
    } else {
      preC[i] = preC[i-k] + 2 * arr[i];
    }
    //cerr << preC[i] << ' ';
  }
  //cerr << '\n';
  for(int i = n;i >= 1;i--) {
    if(i + k > n) {
      sufC[i] = 2 * (l - arr[i]);
    } else {
      sufC[i] = sufC[i+k] + 2 * (l - arr[i]);
    }
    //cerr << sufC[i] << ' ';
  }
  //cerr << '\n';
} 

ll const INF = 1e18;

ll solve(int n, int k, int l) {
  ll ans1 = INF;
  for(int i = 0;i <= n;i++) {
    ans1 = min(ans1, preC[i] + sufC[i+1]);
    //cerr << preC[i] + sufC[i+1] << ' ';
  }
  ll ans2 = INF; 
  //cerr << '\n';
  for(int from = 0;from <= n;from++) {
    int to = min(n+1, from+k+1);
    ans2 = min(ans2, preC[from] + sufC[to] + l);
    //cerr << from << ' ' << to << ' ' << preC[from] + sufC[to] + l << "; ";
  }
  //cerr << '\n';
  return min(ans1, ans2);
}
    

ll delivery(int n, int k, int l, int position[]) {
  for(int i = 0;i < n;i++) {
    arr[i+1] = position[i];
  }
  sort(arr+1, arr+n+1);
  buildPreSufC(n, k, l);
  return solve(n, k, l);
}

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