Submission #421966

#	Time	Username	Problem	Language	Result	Execution time	Memory
421966		Hegdahl	모임들 (IOI18_meetings)	C++17	19 / 100	2133 ms	786436 KiB

meetings

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
  int n = (int)h.size();
  int q = (int)l.size();
  vector<ll> ans(q);

  vector<vector<ll>> side_cost(n);
  for (int i = 1; i < n-1; ++i) {
    if (h[i-1] <= h[i]) continue;
    if (h[i+1] < h[i]) continue;

    side_cost[i].resize(n);

    for (int j = i+1, mx = h[i]; j < n; ++j) {
      mx = max(mx, h[j]);
      side_cost[i][j] = side_cost[i][j-1] + mx;
    }
    for (int j = i-1, mx = h[i]; j >= 0; --j) {
      mx = max(mx, h[j]);
      side_cost[i][j] = side_cost[i][j+1] + mx;
    }
  }

  auto solve = [&](int i, int l, int r) {
    ll ans = h[i];
    if (l < i) ans += side_cost[i][l];
    if (r > i) ans += side_cost[i][r];
    return ans;
  };

  for (int qq = 0; qq < q; ++qq) {

    ll lans = h[l[qq]];
    for (int i = l[qq]+1, mx = h[l[qq]]; i <= r[qq]; ++i) {
      mx = max(mx, h[i]);
      lans += mx;
    }

    ll rans = h[r[qq]];
    for (int i = r[qq]-1, mx = h[r[qq]]; i >= l[qq]; --i) {
      mx = max(mx, h[i]);
      rans += mx;
    }

    ans[qq] = min(lans, rans);

    for (int i = l[qq]+1; i < r[qq]; ++i) {
      if (h[i-1] <= h[i]) continue;
      if (h[i+1] < h[i]) continue;
      ans[qq] = min(ans[qq], solve(i, l[qq], r[qq]));
    }
  }

  return ans;
}

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