| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 197572 | AaronNaidu | 선물상자 (IOI15_boxes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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;
}