Submission #1244802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244802		Boas	Meetings (IOI18_meetings)	C++20	4 / 100	5595 ms	1604 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define sz(x) (int)x.size()
#define ALL(x) begin(x), end(x)
#define loop(n, i) for (int i = 0; i < n; i++)
#define rev(n, i) for (int i = n - 1; i >= 0; i--)

typedef signed i32;
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<vi32> vvi32;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

vector<int> s;

int rmax(int i, int l, int r, int ql, int qr)
{
  if (qr < l || r < ql)
    return 0;
  if (ql <= l && r <= qr)
    return s[i];
  int m = (l + r) / 2;
  return max(rmax(2 * i, l, m, ql, qr), rmax(2 * i + 1, m + 1, r, ql, qr));
}

vi minimum_costs(vi32 H, vi32 L, vi32 R)
{
  int Q = sz(L);
  vi C(Q);
  int N = sz(H);
  int treeN = 1;
  while (treeN < N)
    treeN *= 2;
  s.assign(2 * treeN, {});
  loop(N, i)
  {
    s[i + treeN] = H[i];
  }
  rev(treeN, i)
  {
    s[i] = max(s[2 * i], s[2 * i + 1]);
  }
  for (int j = 0; j < Q; ++j)
  {
    int l = L[j];
    int r = R[j];
    int best = 1e18;
    for (int x = l; x <= r; x++)
    {
      int cur = 0;
      int mxCur = 0;
      for (int i = x; i <= r; i++)
      {
        mxCur = max(mxCur, (i64)H[i]);
        cur += mxCur;
      }
      mxCur = 0;
      for (int i = x; i >= l; i--)
      {
        mxCur = max(mxCur, (i64)H[i]);
        cur += mxCur;
      }
      cur -= H[x];
      best = min(best, cur);
    }
    C[j] = best;
  }
  return C;
}

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