Submission #784777

#	Time	Username	Problem	Language	Result	Execution time	Memory
784777		aZvezda	Meetings (IOI18_meetings)	C++14	4 / 100	5598 ms	2172 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef local
#define cerr if(false)cerr
#endif

const int MAX_N = 1e6 + 10;
int n, q, arr[MAX_N];

ll solve(ll l, ll r) {
	if(r < l) { return 0; }
	if(l == r) { return arr[l]; }
	int mx = max_element(arr + l, arr + r + 1) - arr;
	ll ret = arr[mx] * (r - l + 1);
	ll lft = solve(l, mx - 1) + (r - mx + 1) * arr[mx];
	ll rght = solve(mx + 1, r) + (mx - l + 1) * arr[mx];
	return min({ret, lft, rght});
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	vector<ll> ret = {};
	int q = l.size();
	int n = h.size();
	for(int i = 0; i < n; i ++) {
		arr[i] = h[i];
	}
	for(int i = 0; i < q; i ++) {
		ret.push_back(solve(l[i], r[i]));
	}
	return ret;
}

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