제출 #1265641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265641		julia_08	선물상자 (IOI15_boxes)	C++20	10 / 100	0 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 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);
  
    cost[i] = dist(0, p[i], L) + dist(p[i], p[nxt], L) + dist(p[nxt], 0, L);

  }

  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];

    if(r > 0) 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