제출 #238781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238781		Jatana	모임들 (IOI18_meetings)	C++17	19 / 100	5557 ms	11140 KiB

meetings

#include "meetings.h"
#include <algorithm>
#define le(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define f(i, n) for (int i = 0; i < (n); i++)

using namespace std;

typedef long long ll;

vector<int> H;
vector<ll> dp[2];
vector<int> L;
vector<int> R;
vector<ll> rez;
vector<vector<int>> qs;

void go(int l, int r) {
	if (l >= r) return;
	if (l + 1 == r) {
		f(t, 2) {
			dp[t][l] = H[l];	
		}
		for (int id : qs[l]) {
			rez[id] = H[l];
		}
		return;
	}
	int m = l;
	for (int i = l; i < r; i++)
		if (H[i] > H[m]) 
			m = i;
	go(l, m);
	go(m + 1, r);
	for (int id : qs[m]) {
		// either left or right
		rez[id] = min(
			dp[0][R[id]] + 1LL * H[m] * (m - L[id] + 1),
			dp[1][L[id]] + 1LL * H[m] * (R[id] - m + 1)
		);
	}
	dp[0][m] = (m - 1 >= l ? dp[0][m - 1] : 0) + H[m];
	for (int i = m + 1; i < r; i++) {
		dp[0][i] = min(
			dp[0][i] + 1LL * (m - l + 1) * H[m],
			dp[0][m] + 1LL * (i - m) * H[m]
		);
	}
	dp[1][m] = (m + 1 < r ? dp[1][m + 1] : 0) + H[m];
	for (int i = m - 1; i >= l; i--) {
		dp[1][i] = min(
			dp[1][i] + 1LL * (r - m) * H[m],
			dp[1][m] + 1LL * (m - i) * H[m]
		);
	}
}

vector<ll> minimum_costs(vector<int> _H, vector<int> _L,
    vector<int> _R) {
	L = _L;
	R = _R;
	H = _H;
	dp[0].resize(le(H));
	dp[1].resize(le(H));
	qs.resize(le(H));
  int Q = L.size();
	for (int i = 0; i < Q; i++) {
		int pos = max_element(H.begin() + L[i], H.begin() + R[i] + 1) - H.begin();
		qs[pos].pb(i);
	}
	rez.resize(Q, (ll)1e18);
	go(0, le(H));
  return rez;
}

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