| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 197572 | AaronNaidu | Boxes with souvenirs (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
long long delivery(int n, int k, int l, int positions[]) {
long long sum = 0;
long long minSum;
if(k == 1) {
//cout << "In branch\n";
for(int i = 0; i < n; i++) {
//cout << "Value " << positions[i] << "\n";
sum += 2 * min(positions[i], l - positions[i]);
//cout << "Sum now " << sum << "\n";
}
return sum;
}
sort(positions, positions + n);
/*long long zeroes;
for (int i = 0; i < n; i++)
{
if(positions[i] == 0) {
zeroes++;
}
else {
break;
}
}
n -= zeroes;*/
for (int i = 0; i < n; i++)
{
positions[i] = positions[i+zeroes];
}
if(k >= n) {
if(positions[0] > (double) l/2) {
return 2 * (l - positions[0]);
}
if(positions[n-1] < (double) l/2) {
return 2 * positions[n-1];
}
for(int i = 0; i < n-1; i++) {
if(positions[i+1] - positions[i] > double(l/2)) {
return 2 * (positions[i] + (l - positions[i+1]));
}
}
return l;
}
long long bestSum = n * l;
if(positions[0] > (double) l/2) {
int delivered = 0;
int counter = 0;
while(delivered < n) {
delivered += k;
sum += 2 * (l - positions[counter]);
counter += k;
}
return sum;
}
if(positions[n-1] < (double) l/2) {
int delivered = 0;
int counter = 0;
reverse(positions, positions + n);
while(delivered < n) {
delivered += k;
sum += 2 * positions[counter];
counter += k;
}
return sum;
}
long long remainde = n%k;
long long trial = 0;
long long trial2 = 0;
long long point = -1;
sum = 0;
long long trialNew = 0;
if (remainde)
{
//cout << "Was remainder\n";
//cout << "It's " << positions[remainde - 1] << "vs" << n- positions[n-remainde] << "\n";
//if (positions[remainde - 1] < l - positions[n-remainde]) {
if(true) {
bool firstHalf = false;
//cout << "Cut out first \n";
sum += min(2 * positions[remainde - 1], l);
//cout << "Initial sum " << sum << "\n";
for (int i = remainde; i < n; i++) {
point++;
if(point % k == 0) {
trial = 2 * min(positions[i], l - positions[i]);
if(positions[i] < double (l/2)) {
firstHalf = true;
}
else {
firstHalf = false;
}
//cout << "Start with distance " << trial << "\n";
}
trial2 = 2 * min(positions[i], l - positions[i]);
trial = max(trial, trial2);
if(point % k == k-1 or i == n-1 or positions[i+1] - positions[i] > double(l/2)) {
trial2 = 2 * min(positions[i], l - positions[i]);
//cout << "End with distance " << trial << "\n";
trial = max(trial, trial2);
if(firstHalf and positions[i] > double (l/2)) {
sum += l;
}
else {
sum += trial;
}
point = -1;
}
}
}
if(true) {
bool firstHalf = false;
minSum = sum;
sum = 0;
sum += min(l, 2 * (n - positions[n-remainde]));
for (int i = 0; i < n-remainde; i++) {
point++;
if(point % k == 0) {
trial = 2 * min(positions[i], l - positions[i]);
if(positions[i] < double (l/2)) {
firstHalf = true;
}
else {
firstHalf = false;
}
}
trial2 = 2 * min(positions[i], l - positions[i]);
trial = max(trial, trial2);
if(point % k == k-1 or i == n-1-remainde or positions[i+1] - positions[i] > double(l/2)) {
trial2 = 2 * min(positions[i], l - positions[i]);
trial = max(trial, trial2);
if(firstHalf and positions[i] > double (l/2)) {
sum += l;
}
else {
sum += trial;
}
point = -1;
}
}
}
minSum = min(minSum, sum);
return minSum;
}
else {
bool firstHalf = false;
for (int i = 0; i < n; i++)
{
point++;
if(point % k == 0) {
trial = 2 * min(positions[i], l - positions[i]);
if(positions[i] < double (l/2)) {
firstHalf = true;
}
else {
firstHalf = false;
}
}
trial2 = 2 * min(positions[i], l - positions[i]);
trial = max(trial, trial2);
if(point % k == k-1 or i == n-1 or positions[i+1] - positions[i] > double(l/2)) {
trial2 = 2 * min(positions[i], l - positions[i]);
trial = max(trial, trial2);
if(firstHalf and positions[i] > double (l/2)) {
sum += l;
}
else {
sum += trial;
}
point = -1;
}
}
return sum;
}
for(;;) {
}
return n;
}