Submission #1265644

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

boxes

#include <bits/stdc++.h>
#include "boxes.h"

using ll = long long;

using namespace std;

const ll INF = 1e18;

ll dist(ll i, ll j, int L){

  if(i > j) swap(i, j);
  return min(j - i, L - (j - i));

}

ll dist_c(ll i, ll j, int L){

  // has to be clockwise
  if(i < j) return (j - i);
  return L - (j - i);

}

ll delivery(int n, int K, int L, int p_[]){

  vector<ll> p(2 * n);

  for(int i=0; i<n; i++) p[i] = p_[i];

  for(int i=n; i<(2 * n); i++) p[i] = p[i - n];

  vector<ll> cost(2 * n, 0);

  for(int i=0; i<(2 * n); i++){

    int nxt = min(2 * n - 1, i + K - 1);
  
    if(nxt - i > 1){
      cost[i] = dist(0, p[i], L) + dist_c(p[i], p[nxt], L) + dist(p[nxt], 0, L);
    } else cost[i] = dist(0, p[i], L) + dist(p[i], p[nxt], L) + dist(p[nxt], 0, L);

    // cout << i << " -> " << cost[i] << endl;

  }

  vector<ll> sum(2 * n + 1, 0);

  for(int i=(2 * n - 1); i>=0; i--){

    int nxt = min(2 * n - 1, i + K - 1);

    sum[i] = sum[nxt + 1] + cost[i];

  }

  ll ans = INF;

  for(int i=0; i<n; i++){

    int r = n % K;

    ll cur_ans = sum[i] - sum[i + n - r];

    // cout << "starting at " << i << " " << cur_ans << endl;

    if(r > 0){
      if(r > 2){
        cur_ans += dist(0, p[i + n - r], L) + dist_c(p[i + n - r], p[i + (n - 1)], L) + dist(p[i + (n - 1)], 0, L);
      } else cur_ans += dist(0, p[i + n - r], L) + dist(p[i + n - r], p[i + (n - 1)], L) + dist(p[i + (n - 1)], 0, L);
    }

    ans = min(ans, cur_ans);

  }

  return ans;

}

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