Submission #1222829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222829		madamadam3	Meetings (IOI18_meetings)	C++20	19 / 100	1281 ms	851968 KiB

meetings

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

using namespace std;

typedef long long ll;

const ll INF = 1e18;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  int Q = L.size();
  int n = H.size();
  vector<ll> C(Q);

  vector<int> queries(Q); iota(queries.begin(), queries.end(), 0); 
  sort(queries.begin(), queries.end(), [&](int a, int b) {return R[a] < R[b];}); 

  vector<vector<ll>> left_stacks(n), right_stacks(n);
  vector<ll> stL(n, 0), stR(n, 0);
  int cur_query = 0;
  for (int i = 0; i < n; i++) {
    int cur_idx = i - 1;
    while (cur_idx >= 0 && stL[cur_idx] < H[i]) {
      stL[cur_idx] = H[i];
      cur_idx--;
    }

    stL[i] = H[i];
    left_stacks[i] = stL;
  }

  for (int i = n-1; i >= 0; i--) {
    int cur_idx = i+1;
    while (cur_idx < n && stR[cur_idx] < H[i]) {
      stR[cur_idx] = H[i];
      cur_idx++;
    }

    stR[i] = H[i];
    right_stacks[i] = stR;
  }

  for (int st = 0; st < n; st++) {
    for (int i = 1; i < n; i++) {
      left_stacks[st][i] += left_stacks[st][i-1];
    }
    for (int i = n - 2; i >= 0; i--) {
      right_stacks[st][i] += right_stacks[st][i+1];
    }
  }

  for (int j = 0; j < Q; ++j) {
    ll best = INF;

    for (int i = L[j]; i <= R[j]; i++) {
      ll lv = left_stacks[i][i], rv = right_stacks[i][i];
      ll lsub = L[j] == 0 ? 0 : left_stacks[i][L[j] - 1], rsub = R[j] == n - 1 ? 0 : right_stacks[i][R[j] + 1];

      lv -= lsub; rv -= rsub;
      best = min(best, lv + rv - H[i]);
    }
    C[j] = best;
  }

  return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40