Submission #1265709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265709		julia_08	Boxes with souvenirs (IOI15_boxes)	C++20	20 / 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 delivery(int n, int K, int L_, int p_[]){

  ll L = L_;

  vector<ll> p(n);

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

  vector<ll> cost(n, 0);

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

    int j = max(0, i - K + 1);
  
    cost[i] = min({L, 2 * p[i], 2 * (L - p[j])});

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

  }

  vector<ll> sum(n, 0);

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

    int j = max(0, i - K + 1);

    sum[i] = (j == 0 ? 0 : sum[j - 1]) + cost[i];

  }

  ll ans = INF;

  for(int i=0; i<(K - 1); i++){

    // brutando o que passa pelo 0

    int j = n - K + i + 1;

    ll cur_ans = min(L, 2 * (p[i] + L - p[j]));

    int r = (j - i - 1) % K;

    cur_ans += sum[j - 1] - sum[i + r];

    // cost do [i + 1, i + r]
    if(r > 0) cur_ans += min({L, 2 * p[i + r], 2 * (L - p[i + 1])});

    // cout << i << " " << j << " -> " << cur_ans << endl;


    ans = min(ans, cur_ans);

  }

  ans = min(ans, sum[n - 1]);

  return ans;

}

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